Số nguyên tố cùng nhau

Bách khoa toàn thư mở Wikipedia

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

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%.[4]

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 | 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 Zn*.

Mở rộng cho n số nguyên[sửa | sửa mã nguồ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. 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.

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.

Tham khảo[sửa | sửa mã nguồn]

  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 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. ^ This theorem was proved by Ernesto Cesàro in 1881. For a more rigorous proof than the intuitive and informal one given here, see G.H. Hardy; E. M. Wright (2008). An Introduction to the Theory of Numbers (ấn bản 6). Oxford University Press. ISBN 978-0-19-921986-5., theorem 332.