Combinatorics

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 (a,b) sao cho 1\le a,b\le ngcd(a,b)>1“.

Với phân tích chính tắc a=p_1^{\alpha_1}p_2^{\alpha_2}....p_1^{\alpha_n}, nếu b thỏa mãn gcd(a,b)>1 thì b chia hết ít nhất một trong các ước nguyên tố p_1,p_2,...,p_m của a. Số các số b như vậy nằm từ 1 đến n là:

m(b)=\sum_{i=1} [\frac{n}{p_i}]-\sum_{p_i<p_j} [\frac{n}{p_ip_j}]+...+(-1)^m[\frac{n}{p_1p_2...p_m}].

Lần lượt cho a nhận giá trị từ 1 đến n và lấy tổng các giá trị m(b), chú ý số lần lặp của số hạng (-1)^m[\frac{n}{p_1p_2...p_m}] đúng bằng số các số nằm từ 1 đến n chia hết cho p_1p_2...p_m, và bằng [\frac{n}{p_1p_2...p_m}].

Do đó, theo quy tắc cộng dễ dàng thu được số các bộ (a,b) thỏa mãn gcd(a,b)=11\le a,b\le n

n^2-\sum_{i=1}([\frac{n}{p_i}])^2+\sum_{p_i<p_j} ([\frac{n}{p_ip_j}])^2-...+(-1)^{m-1}([\frac{n}{p_1p_2...p_m}])^2

trong đó p_1,p_2,...,p_m các các số nguyên tố từ 1 đến 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à 1-\frac{1}{{p^2 }}. Từ đó ta có xác xuất cần tính sẽ là

P = \left( {1 - \frac{1}{{2^2 }}} \right)\left( {1 - \frac{1}{{3^2 }}} \right)\left( {1 - \frac{1}{{5^2 }}} \right)\left( {1 - \frac{1}{{7^2 }}} \right)...
Ta lại chú ý công thức

\frac{1}{{1 - x}} = 1 + x + x^2 + x^3 + ...nên ta viết lại P dưới dạng

P = \left( {\left( {1 + 1/2^2 + 1/2^4 + 1/2^6 + ...} \right)\left( {1 + 1/3^2 + 1/3^4 + 1/3^6 + ...} \right)...} \right)^{ - 1}.

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ố n = 2^{\alpha _1 } 3^{\alpha _2 } ...p_i ^{\alpha _i }.

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

P = \left( {1 + \frac{1}{{2^2 }} + \frac{1}{{3^2 }} + \frac{1}{{4^2 }} + ...} \right)^{ - 1}=\frac{1}{{\zeta (2)}} = \frac{6}{{\pi ^2 }}.

(update from http://mathvn.org)