- Hàm phi () Euler của một số nguyên dương được định nghĩa là số các số nguyên dương không vượt quá sao cho .
- Ví dụ, số 10 có 4 số nguyên dương không vượt quá 10 và nguyên tố cùng nhau với 10, đó là 1, 3, 7, 9. Như vậy, .
- Nếu là số nguyên tố, dễ thấy .
- Nếu thì .
- Chứng minh: Có tổng cộng số nguyên dương cần xét. Trong số đó, các số có ước chung lớn nhất với khác 1 sẽ có dạng , với là bất cứ số nguyên dương nào đảm bảo , như vậy có tổng cộng giá trị như thế. Suy ra số các số nguyên tố cùng nhau với là . (QED)
- Nếu (với ) thì .
- Chứng minh: Có tổng cộng số nguyên dương cần xét. Trong số đó, các số có ước chung lớn nhất với khác 1 sẽ có dạng hoặc sao cho . Trong trường hợp đầu, trải dài từ đến . Trong trường hợp sau, trải dài từ đến . Tuy nhiên, có hai giá trị được đếm hai lần, đó là . Như vậy có tổng cộng số không nguyên tố cùng nhau với . Như vậy:
- Nếu (với nguyên tố cùng nhau) thì (trường hợp tổng quát hơn của định lý trước).
- Chứng minh: Tất cả các số nguyên dương không vượt quá có dạng với là các số nguyên lần lượt nằm trong khoảng và .
Công việc cần làm là đếm xem có bao nhiêu cặp giá trị thỏa bài toán.
Bước 1: Chọn . Nhận thấy rằng , nếu không, và suy ra . Xét việc chọn các giá trị thỏa mãn , có tổng cộng giá trị như thế.
Bước 2: Chọn . Với mỗi giá trị đã chọn, có tổng cộng số cần phải xét, với chạy từ đến . Vì và nguyên tố cùng nhau nên các số , , , , khi đem chia cho lấy phần dư sẽ cho ra các kết quả đôi một khác nhau, tạo nên tập hợp . Ta cần chọn ra các giá trị nguyên tố cùng nhau với . Trong trường hợp đó, kết quả phải ra một số nguyên tố cùng nhau với và khác 0. Có giá trị để tạo ra các giá trị như thế.
Các số nguyên được chọn qua hai bước sẽ vừa nguyên tố cùng nhau với và , mặt khác , nên chúng cũng nguyên tố cùng nhau với . Áp dụng quy tắc nhân thì có số. (QED)
- Chứng minh: Tất cả các số nguyên dương không vượt quá có dạng với là các số nguyên lần lượt nằm trong khoảng và .
Công việc cần làm là đếm xem có bao nhiêu cặp giá trị thỏa bài toán.
- Định lý Euler: Với mọi số nguyên dương nguyên tố cùng nhau với , ta có:
Định lý nhỏ Fermat chỉ ra rằng nếu là một số nguyên tố thì:
Nếu thì ta có . Đây là một trường hợp nhỏ của định lý Euler với