Định lý Euler phát biểu rằng nếu a và n là 2 số nguyên tố cùng nhau, thì:

a mũ Phi(n) mod n dư 1

a mũ n mod phi(n) dư Phi(n)

a mũ n mod phi(n) dư 1

a mũ n-1 mod n phi 1