Station - Modulare Potenz
Potenzbildung modulo einer vorgegebenen Zahl
Vorgegeben sei eine natürliche Zahl n. Eine natürliche Zahl a wird mit einer natürlichen Zahl x modulo n potenziert, indem man sie mit x potenziert und anschließend von der Potenz den Rest bei der Division durch n berechnet. Das Ergebnis ist also [ax]%n. Beachte, dass das Ergebnis bei der Potenzbildung modulo n immer eine Zahl kleiner als n ist.
Aufgabe 1
(a) Berechne [84]%5. Berechne auch [([([([8]%5)*8]%5)*8]%5)*8]%5. Was stellst du fest?
(b) Welche Vorteile ergeben sich bei großen Zahlen, wenn man [ax]%n wie folgt berechnet:[(...([([a]%n)*a]%n)...)*a]%n
Aufgabe 2
Berechne [a(p-1)]%p für verschiedene natürliche Zahlen a und verschiedene Primzahlen p. Für welche Zahlen erhält man als Ergebnis 1?
p = 23 a = 42 print( a**(p-1)%p )
Satz (Kleiner Fermatscher Satz)
Sei p eine Primzahl und a eine natürliche Zahl, die kein Vielfaches von p ist. Dann gilt
[a(p-1)]%p = 1
Die Aussage dieses Satzes ist nicht offensichtlich. Eine vollständige Begründung kann hier auch nicht geliefert werden. Die folgenden Überlegungen sollen den Zusammenhang zumindest in Teilen begründen.
Gegeben sei eine Primzahl p und eine natürliche Zahl, die kein Vielfaches von p ist (z.B. p=5 und a = 12). Wenn man [1*a]%p, [2*a]%p, [3*a]%p, ..., [(p-1)*a]%p berechnet, so erhält man als Ergebnisse die Zahlen 1, 2, 3, ..., p-1 - allerdings in anderer Reihenfolge. Probiere das selbst einmal mit den gegebenen Zahlen (und auch anderen) aus.
Hieraus lässt sich mit einigen Rechengesetzen folgender Zusammenhang herleiten:
[(1*a)*(2*a)*(3*a)*...*((p-1)*a)]%p = [1*2*3*...*(p-1)]%p
Umgeformt erhält man:
[1*2*3*...*(p-1)*a(p-1)]%p = [1*2*3*...*(p-1)]%p
Mit einigen zusätzlichen Überlegungen kann man jetzt schließen:
[a(p-1)]%p = 1
