Teorema ini juga disebut dengan Teorema Euler atau Teorema Total Euler.

Jika $a$ dan $n$ adalah bilangan yang koprima maka berlaku:

$$a^{\varphi(n)} \equiv 1 \pmod{n}$$

$\varphi(n)$ adalah fungsi phi Euler atau disebut juga sebagai Euler totien function.

# Fungsi Phi Euler

Fungsi ini menghitung jumlah bilangan sebelum bilangan masukan yang koprima dengan bilangan masukan.

Fungsi ini memiliki sifat seperti berikut:

• $\varphi(1) = 1$
• $\varphi(2) = 1$
• $\varphi(p) = p - 1$ untuk $p$ bilangan prima
• $\varphi(mn) = \varphi(m)\varphi(n)$ jika FPB $m$ dan $n$ adalah 1 ($m$ dan $n$ koprima).

Berikut adalah nilai fungsi ini dari 1 sampai 10:

Secara umum, untuk menghitung nilai dari fungsi ini kita dapat menggunakan sifat seperti berikut:

Semua bilangan dapat kita tuliskan sebagai perkalian bilangan prima penyusunnya.

$$n=\left(p_{1}\right)^{k1}\left(p_{2}\right)^{k2}\ldots\left(p_{r}\right)^{kr}$$

$p_1, p_2, \ldots, p_r$ adalah bilangan prima.

Maka nilai fungsi phi Euler untuk $n$ adalah:

$$\varphi(n)=n\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right)\ldots\left(1-\frac{1}{p_{r}}\right)$$

Contoh penggunaanya menghitung nilai $\varphi(18)$.

$$18 =2\times3^{2}$$

$$\begin{aligned} \varphi(18) & =18\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\\ & =18\frac{1}{2}\frac{2}{3}\\ & =6 \end{aligned}$$

Contoh menghitung nilai $\varphi(1000)$

$$\begin{aligned} 1000 & =10^{3}\\ & =(2\times5)^{3}\\ & =2^{2}5^{3} \end{aligned}$$

$$\begin{aligned} \varphi(1000) & =1000\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)\\ & =1000\frac{1}{2}\frac{4}{5}\\ & =1000\frac{2}{5}\\ & =400 \end{aligned}$$