Satz von Euler

16.11.2013, 21:12	Danny92	Auf diesen Beitrag antworten »
Satz von Euler Meine Frage: Hallo liebe Leute, ich suche eine Möglichkeit, $\begin{eqnarray} 2^{50001} mod 100003 \end{eqnarray}$ zu bestimmen. Ich habe mir bereits den Satz von Euler, den kleinen fermatschen Satz sowie die Eulersche Phi-Funktion angeschaut, wusste mir damit jedoch noch nicht zu helfen. Meine Ideen: Nach dem Satz von Euler ist $\begin{eqnarray} a^{b} \equiv a^{b mod phi(n)} (mod n) \end{eqnarray}$ Sei n jedoch eine sehr hohe Primzahl, würde das Bestimmen von Phi programmtechnisch zu lange dauern. Meine Frage ist nun, mit welchem Trick man sich behelfen könnte, um das schnell und einfach zu bestimmen?
16.11.2013, 21:50	MatheIstLustig	Auf diesen Beitrag antworten »
RE: Satz von Euler Für Primzahlen p gilt: $\begin{eqnarray} \phi (p)=p-1 \end{eqnarray}$
16.11.2013, 22:05	Danny92	Auf diesen Beitrag antworten »
RE: Satz von Euler Ja das stimmt, aber ich weiß nicht, ob n eine Primzahl ist.
16.11.2013, 22:15	MatheIstLustig	Auf diesen Beitrag antworten »
RE: Satz von Euler Bei so kleinen Zahlen ist das schnell im Internet nachgeschaut. z.B. Primzahltabelle
17.11.2013, 20:01	Danny92	Auf diesen Beitrag antworten »
RE: Satz von Euler Ja aber das ist nur ein Beispiel. Nehmen wir an, n sei eine beliebig große Zahl, von der ich nicht so schnell ohne weiteres wissen kann, ob sie prim ist oder nicht. Was dann?
17.11.2013, 20:25	MatheIstLustig	Auf diesen Beitrag antworten »
RE: Satz von Euler Mit enem Rechner lassen sich derartige Aufgaben auch für große Zahlen relativ schnell berechnen. Wenn du mit der Hand rechnest kann das Rechenintensiv sein. Für einen Algorithmus kannst du z.B. nach dem Stichwort Binäre Exponentiation suchen.
Anzeige

17.11.2013, 20:32	HAL 9000	Auf diesen Beitrag antworten »
@Danny92 Es ist ja schön, dass du dir derartige Sorgen machst, aber zum einen geht es bei solchen Aufgaben eigentlich nie um "beliebig große" Zahlen. Und zum anderen liegt der inhaltliche Fokus bei dieser speziellen Aufgabe hier ganz woanders: M.E. nämlich beim 2.Ergänzungssatz zum Quadratischen Reziprozitätsgesetz.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »