Funkcja $\phi$ Eulera
Niech $\phi(n)$ oznacza liczbę liczb naturalnych nie większych od liczby naturalnej $n$ i względnie pierwszych z $n$.
Dla liczby $1$ otrzymujemy $\phi(1)=1$, dla liczby $2$ mamy $\phi(2)=1$, bo tylko liczba $1$ jest względnie pierwsza z $2$.
$\phi(3)=2$, bo spośród liczb $1,2,3$ względnie pierwsze z $3$ są dwie liczby $1$ i $2$.
$\phi(4)=2$, bo spośród liczb $1,2,3,4$ tylko $1$ i $3$ są względnie pierwsze z $4$.
$\phi(5)=4$, bo spośród liczb $1,2,3,4,5$ względnie pierwsze z $5$ są cztery liczby $1, 2, 3, 4$.
$\phi(6)=2$, bo spośród liczb $1,2,3,4,5,6$ tylko $1$ i $5$ są względnie pierwsze z $6$.
Dalej otrzymujemy $\phi(7)=6$, $\phi(8)=4$, $\phi(9)=6$, $\phi(10)=4$, $\phi(11)=10$, itd.
Jeśli liczba $n$ jest liczbą pierwszą, to wszystkie liczby naturalne mniejsze od liczby $n$ są względnie pierwsze z $n$, stąd $\phi(n) = n-1$. Implikacja działa w drugą stronę, tzn. jeśli liczba naturalna $n$ spełnia $\phi(n) = n-1$, to jest liczbą pierwszą. Jeśli natomiast liczba $n$ jest złożona, to ma taki dzielnik $d$, że $1 \lt d \lt n$ i z liczb ciągu $1,2,3,\ldots, n$ co najmniej dwie, mianowicie $d$ oraz $n$ nie są względnie pierwsze z $n$, skąd mamy $\phi(n) \lt n-1$.
Jeśli rozkład na czynniki pierwsze liczby $n$ równy jest $n= p^{a_1}_1 p^{a_2}_2 \ldots p^{a_k}_k$, to
$\phi(n) = n(1 -\frac{1}{p_1})(1 -\frac{1}{p_2}) \ldots (1 -\frac{1}{p_k})$
lub równoważnie $\phi(n) = p^{a_1-1}_1 p^{a_2-1}_2 \ldots p^{a_k-1}_k(p_1-1)(p_2-1)\ldots(p_k-1)$.