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: E(n) = (p-1) * (q-1) Przyspiesza to znacznie obliczenia, przy operacjach na duzych liczbach.