phi(x) sei die Eulersche Phi-Funktion, die die Anzahl der n aus N bezeichnet, die kleiner als x und mit x teilerfremd sind. Ist nicht weiter wichtig, interessant ist nur, daß für zwei Primzahlen p und q gilt:
phi(p*q)=(p-1)*(q-1).
Es gilt
a^(phi(z)) = 1 (mod z) [ = bedeutet: ,kongruent modulo\' ]
also auch:
a^(phi(z)+1) = a (mod z) (a