Satz von Euler

Satz von Euler

Der Satz von Euler lautet:

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

Er gilt unter der Bedingung $\mathrm{ggT}(a,n)=1$, mit $a,n\in \mathbb{N}$, wobei $\mathrm{ggT}$ der größte gemeinsame Teiler der beiden natürlichen Zahlen $a$ und $n$ ist und $\phi (n)$ die eulersche φ-Funktion bezeichnet, nämlich die Anzahl der zu $n$ teilerfremden Reste modulo $n$.

Für prime Moduli $p$ gilt $\phi (p)=p-1$, also geht für sie der Satz von Euler in den kleinen Satz von Fermat über.