Die primen Restklassengruppen

Es sei $n > 1$ eine natürliche Zahl und $(Z/(n),+,*)$ der Restklassenring der ganzen Zahlen modulo $n$ . Weiterhin sei $G(n)$ die Gruppe der Einheiten des multiplikativen Monoids $(Z/(n),*,1)$ . Man nennt diese (offensichtlich abelsche) Gruppe, die prime Restklassengruppe modulo $n$ . Dabei liegt die Restklasse $[a]$ (mit $0 <= a < n$ ) aus $Z/(n)$ genau dann in $G(n)$ , wenn $a$ und $n$ teilerfremd sind, d. h. wenn $ggT(a,n) = 1$ gilt. Für $d = ggT(a,n)$ existieren nämlich ganze Zahlen $x$ und $y$ mit $x*a + y*n = d$ , wie man aus der Anwendung des euklidischen Algorithmus zur Bestimmung von $d$ ersieht. Hieraus ergibt sich in $Z/(n)$ die Gleichung $[x][a] = [d]$ . Für $d = 1$ zeigt dies gerade die Invertierbarkeit von $[a]$ . Für $d > 1$ gibt es aber eine ganze Zahl $m$ mit $n = m*d$ und $0< m < n$ . Es folgt $[m]*[a] = [m*a] = [m*d*b] = [0]$ für $a = d*b$ , d. h. in diesem Fall ist $[a]$ Nullteiler und damit sicherlich nicht invertierbar.

Man bezeichnet mit $phi(n)$ die Ordnung von $G(n)$ und nennt diese Funktion die Eulersche phi-Funktion. Nach den obigen Überlegungen ist $phi(n)$ gerade die Anzahl der zu $n$ teilerfremden Zahlen aus der Menge ${ 1, 2, ..., n-1 }.$ Dabei sind genau für eine Primzahl $n$ alle diese Zahlen zu $n$ teilerfremd, so daß für alle natürlichen Zahlen $n > 1$ gilt

(1) $n ist prim <=> phi(n) = n-1.$

Satz (Euler) Sind $a$ und $n > 1$ ganze Zahlen mit $ggT(a,n) = 1$ , so gilt

(2) $a$ ^phi(n) = 1 modulo n.

Beweis: Wegen $ggT(a,n) = 1$ ist $[a]$ in der primen Restklassengruppe $G(n)$ enthalten und diese hat die Ordnung phi(n). Aus dem Satz von Lagrange folgt $ord(<[a]>) | phi(n)$ für die Ordnung $ord([a]) = ord(<[a]>)$ der von $[a]$ erzeugten zyklischen Untergruppe von $G(n)$ . Hieraus folgt $[1] = [a]$ ^phi(n) in $G(n)$ bzw. in $Z/(n)$ . Dies ist aber gerade (2).