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à  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à  và xác suất để ít nhất một trong hai không chia hết đó là  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   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ố:

 

Ở đâ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  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 , 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à

Xem thêm
 Số nguyên tố

Tham khảo

Lý thuyết số