Algebra: Potenzieren in Restklassen: Was ist 2^99999 mod 99991?
Ich soll ein a element {0,...,99990} bestimmen, mit 2^99999 kongruent a mod 99991. Als Hinweis ist gegeben, dass 99991 eine Primzahl ist.
Ich weiß dadurch, das die multiplikative Restklassengruppe zyklisch ist und 99990 Elemente hat. Aber ich weiß doch nicht, ob 2 wirklich ein Erzeuger dieser Gruppe ist, und kann das doch auch nicht ohne weiteres nachprüfen (sonst wäre die Aufgabe doch trivial, mit 2^(99999-99991) = 2^8 =256, oder?)
Kann mir jemand helfen wie ich hier vorgehen kann?
MfG
Edit:
Ich weiß die Gruppe ist zyklisch, das heißt es existiert ein Erzeuger g und ein d mit g^d = 2 und g Element Z/99991Z und d sei die kleine natürliche Zahl, die diese Bedingung erfüllt.
dann gilt doch folgendes:
2^99999 = (g^d)^99999 = (g^d)^99991 * (g^d)^8 = (g^99991)^d *2^8 = 1^d *2^8 = 2^8 = 256
Kann ich nicht auch so argumentieren, ohne zu wissen, dass 2 Erzeuger ist?
3 Antworten
Da 99991 eine Primzahl ist, weißt du zunächst einmal, dass du überhaupt eine multiplikative Gruppe hast.
Die hat 99990 Elemente. Über die Erzeuger musst du dir ehrlich gesagt keine Gedanken machen.
Aus dem Satz von Lagrange folgt, dass die Ordnung von 2 auf jeden Fall ein Teiler von 99990 ist. Und daraus folgt, dass 2^99990 = 1 gilt.
Allerdings hat die Gruppe ja nicht 99991 Elemente - du betrachtest ja nur die multiplikative, nicht die additive Gruppe.
Also (alles modulo gedacht) :
2^99999 = 2^(99999-99990) = 2^9 * 1/2^99990 = 2^9 = 512.
Das bekommt übrigens Wolframalpha auch heraus.
Wenn du den kleinen Satz von Fermat kennst/benutzen darfst ist er hier sehr hilfreich.
Demnach gilt für eine Primzahl p und eine ganze Zahl a=/=0 :1=a^(p-1) mod p.
Wählst du jetzt a=2 kannst du folgende Umformung machen:
2^99999=(2^99999)/1=(2^99999)/(2^ (99991-1))=2^(99999-99990)=2^9=512.
Wenn der modulo und Exponent nicht zufällig so nah beieinander gelegen hätten gibt es effiziente Algorithmen um modulare Potenzen zu berechnen (z.B. https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation , wobei du nach jeder Multiplikation nochmal den mod berechnen musst)
Wissen kann ich es nicht nennen, aber so hätte ich auch gerechnet / argumentiert.
Dazu fällt mir noch der Name Euler ein.