Die Ordnung ordn(m) einer Zahl m modulo n
english

Exponiert man eine ganze Zahl modulo einer anderen, so kann man merkwürdige Effekte beobachten. Beispielsweise gilt 33 = 27 = 12 mod 15, während 34 = 81 = 6 mod 15 gilt. D.h., 12 multipliziert mit 3 ergibt modulo 15 eine Zahl, die kleiner als 12 ist!? Oder, wenn man modulo 24 rechnet (die Anzahl der Stunden eines Tages), so erhält man 33 = 27 = 3 mod 24. Komisch, oder?

Für einige Zahlen m > 1 kann man sogar eine Potenz r finden, so dass mr = 1 mod n. Zum Beispiel gilt 42 = 16 = 1 mod 15.

Die Ordnung einer ganzen Zahl m modulo einer (natürlichen) Zahl n ist definiert als die kleinste positive ganzzahlige Potenz r, so dass

mr = 1 mod n.

Man bezeichnet die Ordnung r von m modulo n kurz mit ordn(m). Für einige Konstellationen kann es durchaus passieren, dass gar keine positive Potenz mit dieser Eigenschaft existiert. Wir haben oben gesehen, dass 33 = 3 mod 24, d.h., 33 = 31 mod 24, und wir berechnen direkt 32 = 34 = 9 mod 24. Jede gerade Potenz von 3 ergibt also 9 modulo 24, jede ungerade Potenz ergibt 3 modulo 24.

Schlimmer noch: Manchmal gibt es Zahlen, deren positive Potenz verschwindet. Betrachten wir z.B. 122 = 144 = 0 mod 24. Für solche Zahlen existiert gar keine positive Potenz, die ihre Ordnung liefern könnte, und die Ordnung ist dann als unendlich definiert.

Ein wichtiges gruppentheoretisches Resultat ist, dass wenn n prim ist, jede Zahl, die n nicht teilt, von endlicher Ordnung ist. Ist beispielsweise n = 7, so kann die Ordnung jeder Zahl aus der folgenden Tabelle abgelesen werden.

m 1 2 3 4 5 6 8 ...
ord7(m) 1 3 6 3 6 2 1 ...

(Die Punkte "..." deuten an, dass sich alles zyklisch wiederholt.) Rechnen Sie es nach! Allgemeiner gilt: Jede zu n teilerfremde Zahl m ist von endlicher Ordnung modulo n, wie z.B. für n=15:

m 1 2 4 7 8 11 13 14
ord15(m) 1 4 2 4 4 2 4 2

Insbesondere sind die möglichen endlichen Ordnungen modulo n Teiler des Werts der Carmichael-Funktion, und umgekehrt sind alle seine Teiler die Ordnung mindestens einer Zahl. Für 15 ergibt die Carmichael-Funktion 4. Und in der Tat sind alle Teiler von 4, also 1, 2 und 4, als Ordnung in der Tabelle vertreten! Sie können hier ein AppletDuke starten, dass u.a. die Ordnung berechnet.


© de Vries 2002 – 2012 federstrich Home