Archive

Posts Tagged ‘Primes’

Xác suất hai số nguyên dương nguyên tố cùng nhau


Đầu tiên xét bài toán: “Tìm số cặp sao cho “.

Với phân tích chính tắc , nếu b thỏa mãn thì b chia hết ít nhất một trong các ước nguyên tố của . Số các số b như vậy nằm từ 1 đến n là:

Lần lượt cho nhận giá trị từ 1 đến và lấy tổng các giá trị m(b), chú ý số lần lặp của số hạng đúng bằng số các số nằm từ 1 đến n chia hết cho , và bằng

Do đó, theo quy tắc cộng dễ dàng thu được số các bộ thỏa mãn

trong đó các các số nguyên tố từ 1 đến

Ta kí hiệu các số các bộ này ứng với n là l(n)

Ta nhận thấy rằng P=1-\lim_{n\to\infty}\frac{l(n)}{n^2} sẽ bằng xác suất để 2 số nguyên dương được chọn ngẫu nhiên là nguyên tố cùng nhau. Ta đi tìm xác suất thú vị này theo một cách khác.

Chú ý là xác suất để hai số tự nhiên ngẫu nhiên ko nhận số nguyên tố p làm ước số sẽ là
Từ đó ta có xác xuất cần tính sẽ là


Ta lại chú ý công thức

nên ta viết lại P dưới dạng

Ta chú ý đến định lí Unique Factorization thì mỗi số tự nhiên điều biểu diễn duy nhất dưới dạng tích các số nguyên tố

Và ta thấy trong tích trên chứa đủ các số có dạng trên nên ta viết lại tích dưới dạng

(update from http://mathvn.org)

Advertisements
Categories: Combinatorics Tags: ,