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ụ 6 và 35 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, hợp số là số nguyên tố cùng nhau. VD: 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.