Funkcja Eulera dla liczby calkowitej dodatniej n, okresla ilosc calkowitych liczb dodatnich mniejszych niz n i wzglednie pierwszych z n. Mowi sie wtedy, ze jest to liczba okreslajaca wielkosc zbioru residuow mod n.

Na przyklad zbior residuow mod 10 to liczby {1,3,7,9}, gdyz nie zawieraja one wspolnego czynnika (roznego od 1) z liczba 10. Zatem E(n) = 4.

Gdy n jest iloczynem dwoch liczb pierwszych (p, q) to zachodzi nastepujaca prawidlowosc:

Przyspiesza to znacznie obliczenia, przy operacjach na duzych liczbach.