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)   aphi(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).