|
Die Ordnung ordn(m) einer Zahl m modulo n
|
|
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 Applet
starten, dass u.a. die Ordnung berechnet.
| © de Vries 2002 – 2012 |
|
|