Số nguyên tố cùng nhau

(Đổi hướng từ Nguyên tố cùng nhau)

Trong toán học, các số nguyên ab đượ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.[1][2] 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.[3]

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

sửa

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

 
Hình 1. Các số 4 và 9 là nguyên tố cùng nhau vì đường chéo không đi qua điểm nguyên nào trong hình chữ nhật

Ta cũng có: nếu ab là nguyên tố cùng nhau và brbs (mod a), thì rs (mod a) (vì ta có thể chia cho b khi theo modulo a). Tiếp theo, nếu ab1 là nguyên tố cùng nhau, và ab2 cũng nguyên tố cùng nhau, thì ab1b2 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 ab 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 ab 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 ab 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

sửa

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

sửa

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

sửa

Chọn ngẫu nhiên hai số nguyên ab, thường dễ có câu hỏi về xác suất mà hai số ab nguyên tố cùng nhau. Để xác định, ta thường dùng tính chất rằng ab 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ả ab (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) 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ố p  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ố pq, một con số chỉ chia hết được cho cả pq khi và chỉ khi nó chia hết cho pq, 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 ζhàm zeta Riemann, định thức liên hệ giữa tích trên các số nguyên tố với ζ(2) là một ví dụ của tích Euler, và giá trị của ζ(2)π2/6 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 PN 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ù PN sẽ không bao giờ bằng chính xác với 6/π2, sau khi làm việc thêm,[4] ta có thể chứng minh rằng giới hạn khi  , xác suất PN tiến tới 6/π2.

Tổng quát hơn, chọn ngẫu nhiên k số nguyên, xác suất mà chúng nguyên tố cùng nhau là  

Xem thêm

sửa

Tham khảo

sửa
  1. ^ “A Treatise on Arithmetic...: James Stewart Eaton: Free Download & Streaming: Internet Archive”. Internet Archive. Truy cập 3 tháng 10 năm 2015.
  2. ^ G.H. Hardy; E. M. Wright (2008). An Introduction to the Theory of Numbers (ấn bản thứ 6). Oxford University Press. tr. 6. ISBN 978-0-19-921986-5.
  3. ^ Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics, Addison-Wesley
  4. ^ Định lý này được chứng minh bởi Ernesto Cesàro trong 1881. Để xem bài chứng minh, đọc Hardy & Wright 2008, Theorem 332