Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

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?

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
X

Fehler melden

X

Suche