Modulo-Rechnung mit Fermat |
23.12.2019, 16:41 | pureGewalt | Auf diesen Beitrag antworten » |
Modulo-Rechnung mit Fermat Guten Abend leute, ich soll die letzten beiden stellen von 2^751 ermitteln. Meine Ideen: Ich habe jetzt den satz von euler Fermat angewendet aber komme nicht auf das gewünschte ergebnis. Und zwar über den Taschenrechner habe ich herausgefunden das die 2^751 mod 100 = 48 sein soll. Somit müssten das die letzten beiden Ziffern sein. meine Rechnung : x^phi(n) kongruent 1 mod n für ggT(x,n) = 1 n = 100 => phi(100) = phi(2) * phi(2) * phi(5) * phi(5) daraus nehme ich dann die teilerfremden 1 * 1 * 4 * 4 = 16 somit => 2^16 konguent 1 mod 100 und egal wie ich diese jetzt aufteile, kommt bei mir immer 36 raus? Ich freue mich über jegliche Hilfe! Liebe Grüße und schöne Feiertage! |
||
23.12.2019, 18:41 | Mathema | Auf diesen Beitrag antworten » |
Das ist gleich doppelt verkehrt. Zunächst mal sind 2 und 100 sicherlich nicht tellerfremd - und auch phi(100) = phi(2) * phi(2) * phi(5) * phi(5) ist verkehrt, viel eher gilt phi(100)= phi(4) * phi(25). Tipp: Du könntest 2^751 mod 4 und 2^751 mod 25 berechnen und anschließend den chinesischen Restsatz benutzen. Dir auch schöne Feiertage! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|