Số nguyên a 1 được gọi là số nguyên tố, nếu a chỉ có ước số là 1 và a. Một số nguyên lớn hơn 1 không là số nguyên tố thì được gọi là hợp số. Ví dụ các số 2, 3, 5, 7 là số nguyên tố; các số 6, 8, 10, 12, 14, 15 là hợp số. Hai số a và b được gọi là nguyên tố cùng nhau, nếu chúng có ước số chung là 1, tức là nếu gcd (a,b) =1