Số nguyên tố cùng nhau

Trong toán học, các số nguyên a và b được gọi là nguyên tố cùng nhau (tiếng Anh: coprime hoặc relatively prime) nếu chúng có Ước số chung lớn nhất là 1. Ví dụ 5 và 2 là nguyên tố cùng nhau vì chúng có ước chung lớn nhất là 1, nhưng 6 và 27 không nguyên tố cùng nhau vì chúng có ước chung lớn nhất là 3. Số 1 là nguyên tố cùng nhau với mọi số nguyên. Nhưng cũng có những trường hợp đặc biệt mà các hợp số là số nguyên tố cùng nhau. Ví dụ: 6 và 25 tuy là hợp số nhưng chúng có ước chung lớn nhất là 1 nên chúng là những số nguyên tố cùng nhau.

Một phương pháp xác định tính nguyên tố cùng nhau của hai số nguyên là sử dụng thuật toán Euclid. Phi hàm Euler của một số nguyên dương n là số các số nguyên giữa 1 và n nguyên tố cùng nhau với n.

Các tính chất

Các điều kiện sau tương đương với điều kiện a và b nguyên tố cùng nhau:

Tồn tại các số nguyên x và y sao cho ax + by = 1 (xem Đẳng thức Bézout).
Số nguyên b là khả nghịch theo modulo a: nghĩa là tồn tại số nguyên y sao cho by ≡ 1 (mod a). Nói cách khác, b là một đơn vị trong vành Z/aZ của các số nguyên modulo a.

Ta cũng có: nếu a và b là nguyên tố cùng nhau và br ≡ bs (mod a), thì r ≡ s (mod a) (vì ta có thể chia cho b khi theo modulo a). Tiếp theo, nếu a và b1 là nguyên tố cùng nhau, và a và b2 cũng nguyên tố cùng nhau, thì a và b1b2 cũng là nguyên tố cùng nhau(vì tích của các đơn vị lại là đơn vị).

Nếu a và b là nguyên tố cùng nhau và a là ước của tích bc, thì a là ước của c. Đây là tổng quát hóa của bổ đề Euclid (nếu p là số nguyên tố, và p là ước của tích bc, thì p là ước của b hoặc p là ước của c.

Hai số nguyên a và b là nguyên tố cùng nhau nếu và chỉ nếu đoạn thẳng nối điểm có tọa độ (a, b) trong Hệ tọa độ Descartes với gốc (0,0), không có điểm nào trên nó có tọa độ nguyên. (Hình 1.)

Xác suất để hai số nguyên chọn ngẫu nhiên là nguyên tố cùng nhau bằng 6/π2 (xem pi), xấp xỉ 60%.Xem dưới để hiểu rõ hơn.

Hai số tự nhiên a và b là nguyên tố cùng nhau nếu và chỉ nếu 2a − 1 và 2b − 1 là nguyên tố cùng nhau.

Ký hiệu nhóm liên quan
Nếu n≥1 là một số nguyên, các tập hợp số nguyên tố cùng nhau với n, lấy theo modulo n, tạo thành một nhóm với phép nhân; nó được ký hiệu là (Z/nZ)× hoặc Zn.

Mở rộng cho nhiều số nguyên
Cho n số nguyên a1, a2,..., an. Các số này được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của n số đó bằng 1.

Cần phân biệt với khái niệm nguyên tố cùng nhau từng đôi một hay đôi một nguyên tố cùng nhau. Các số a1, a2,..., an được gọi là nguyên tố cùng nhau từng đôi một nếu từng cặp hai số khác nhau trong chúng là nguyên tố cùng nhau. Nói cách khác, nguyên tố cùng nhau từng đôi một là điều kiện mạnh hơn của nguyên tố cùng nhau, một dãy số nguyên tố cùng nhau từng đôi một thì cũng sẽ nguyên tố cùng nhau nhưng ngược lại chưa chắc đã đúng

Ví dụ: Ba số 2, 10, 15 là nguyên tố cùng nhau, nhưng không nguyên tố cùng nhau từng đôi một.

Khái niệm nguyên tố cùng nhau từng đôi một trở thành giả thuyết quan trọng trong nhiều kết quả của lý thuyết số, chẳng hạn như định lý thặng dư Trung Quốc.

Khi có vô hạn số, ta vẫn có các dãy thoả mãn điều kiện nguyên tố cùng nhau từng đôi một, chẳng hạn như dãy các só nguyên tố, dãy Sylvester hoặc dãy các số Fermat

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

Chọn ngẫu nhiên hai số nguyên và , thường dễ có câu hỏi về xác suất mà hai số và nguyên tố cùng nhau. Để xác định, ta thường dùng tính chất rằng và nguyên tố cùng nhau khi và chỉ khi không có số nguyên tố nào đồng thời là ước của cả và (xem Định lý nền tảng của số học).

Không chính quy mà nói, xác suất để bất kỳ số nào chia hết cho số nguyên tố (hoặc thậm chí bất kỳ số nguyên) là {{tmath|\tfrac{1}{p};}} bởi vì, tính từ 0 thì cứ 7 số thì số thứ 7 chia hết cho 7. Do đó xác suất mà để cả hai chia hết cho số nguyên tố là {{tmath|\tfrac{1}{p^2},}} và xác suất để ít nhất một trong hai không chia hết đó là {{tmath|1-\tfrac{1}{p^2}.}} Mọi họ hữu hạn các sự kiện chia hết cho các số nguyên tố phân biệt thì đều độc lập với nhau. Ví dụ, trong trường hợp có hai sự kiện chia hết cho số nguyên tố và , một con số chỉ chia hết được cho cả và khi và chỉ khi nó chia hết cho , xác suất chia hết cho cái sau có xác suất {{tmath|\tfrac{1}{pq}.}} Nếu ta dùng heuristic để nhận định rằng lập luận này có thể mở rộng cho vô hạn sự kiện chia hết, thì ta có thể đoán sự kiện mà hai số nguyên tố cùng nhau sẽ được tính trên tích tất cả các số nguyên tố:

: \prod_{\text{prime } p} \left(1-\frac{1}{p^2}\right) = \left( \prod_{\text{prime } p} \frac{1}{1-p^{-2}} \right)^{-1} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2} \approx 0.607927102 \approx 61\%.

Ở đây hàm là hàm zeta Riemann, định thức liên hệ giữa tích trên các số nguyên tố với là một ví dụ của tích Euler, và giá trị của là là kết quả từ bài toán Basel, được giải bởi Leonhard Euler trong 1735.

Không có cách này trong chọn số nguyên dương sao cho mọi số nguyên dương đều xuất hiện với xác suất bằng nhau, nhưng câu "chọn ngẫu nhiên số nguyên" có thể viết chính quy bằng cách sử dụng mật độ tự nhiên. Với mỗi số nguyên dương, ta gọi }} là xác suất mà hai số nguyên được chọn trong tập \{1,2,\ldots,N\} nguyên tố cùng nhau. Mặc dù }} sẽ không bao giờ bằng chính xác với , sau khi làm việc thêm, ta có thể chứng minh rằng giới hạn khi N \to \infty,, xác suất }} tiến tới .

Tổng quát hơn, chọn ngẫu nhiên số nguyên, xác suất mà chúng nguyên tố cùng nhau là {{tmath|\tfrac{1}{\zeta(k)}.}}

Xem thêm
Số nguyên tố

Tham khảo