Funkcja 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).