Teorema Euler

Dalam teori bilangan, teorema Euler (juga dikenal sebagai teorema Fermat-Euler) menyatakan bahwa jika n adalah bilangan bulat positif, dan a adalah prima relatif dengan n, maka

a^φ(n) = 1 (mod n)

di mana φ(n) melambangkan fungsi phi Euler. Biasa pula ditulis

$\varphi (n)=\left\{x|1\leq x\leq n{\mbox{ dengan }}\mathrm {fpb} (x,n)=1\right\},$

dimana fpb Faktor persekutuan terbesar.

Contoh

Untuk $n=p$ prima

$a^{p-1}=1{\pmod {p}},$

karena $\varphi (p)=p-1$. Itu Teorema kecil Fermat.