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.^[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 | sửa mã nguồn]

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.

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 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à b₁ là nguyên tố cùng nhau, và a và b₂ cũng nguyên tố cùng nhau, thì a và b₁b₂ 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/π² (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 2^a − 1 và 2^b − 1 là nguyên tố cùng nhau.

Ký hiệu nhóm liên quan[sửa | sửa mã nguồn]

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 Z_n^*.

Mở rộng cho nhiều số nguyên[sửa | sửa mã nguồn]

Cho n số nguyên a₁, a₂,..., a_n. 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ố a₁, a₂,..., a_n đượ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 | sửa mã nguồn]

Chọn ngẫu nhiên hai số nguyên $a$ và $b$ , thường dễ có câu hỏi về xác suất mà hai số $a$ và $b$ nguyên tố cùng nhau. Để xác định, ta thường dùng tính chất rằng $a$ và $b$ 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ả $a$ và $b$ (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$ là ${\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ố $p$ là ${\tfrac {1}{p^{2}}},$ và xác suất để ít nhất một trong hai không chia hết đó là $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ố $p$ và $q$ , một con số chỉ chia hết được cho cả $p$ và $q$ 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 ${\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 $ζ (2)$ là một ví dụ của tích Euler, và giá trị của $ζ (2)$ là $π 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 $P N$ 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ù $P N$ 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 $N\to \infty ,$ , xác suất $P N$ tiến tới $6/ π 2$ .