Modulares Potenzieren - a^r wird zu groß für Taschenrechner - Lösungsweg funktioniert nicht...?
Folgende Aufgabe...
Mein bisheriger Rechen- und Lösungsweg war eigentlich...
Aber wie man sieht, bin ich daran verzweifelt weil mein bisher genutzter Lösungsweg hier nicht zu funktionieren scheint... Ich bin (wie man ebenfalls sieht...) eine Null in Mathematik, weiß mir deshalb also nicht zu helfen...
HELP please... again...
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Mathematik, rechnen, Mathematiker
Die folgenden Rechnungen modulo 6500
- 11² = 121
- 11^4 = 14641 = 1641
- 11^9 = 1641² * 11 = 1191
- 11^18 = 1191^2 = 1481
- 11^37 = 1481^2 * 11 = 5471
- 11^75 = 5471^2 * 11 = 5751
- 11^150 = 5751^2 = 2001
- 11^300 = 2001^2 = 1
- 11^600 = 1^2 = 1
- 11^1200 = 1^2 = 1
- 11^2401 = 1^2 * 11 = 11
- 11^4803 = 11^2*11 = 1331
- 11^9607 = 1331^2 * 11 = 171
Das ist die Binäre Exponentiation (Square and Multiply)
Woher ich das weiß:Hobby
Schachpapa
05.07.2023, 08:51
@Schachpapa
phi(6500) = 6500/(2*5*13) * (1*4*12) = 6500/130*48 = 50*48=2400
entspricht deinem 6500 * (1 -1/2) * (1-1/5) * (1-1/13)
den letzten Faktor hattest du vergessen
Das war unnötiger Aufwand. Dein Ansatz war richtig, du hast dich nur verrechnet.
phi(6500) = phi(2^2 * 5^3 * 13) = 2^1 * 1 * 5^2 * 4 * 1 * 12 = 2400
(Du hast den Faktor 13 vergessen)
Also ist 11^2400 mod 6500 = 1
9607 = 4 * 2400 + 7
11^9607 mod 6500 = 11^7 mod 6500
Das geht noch locker mit Taschenrechner und führt zum gleichen Ergebnis wie meine aufwendige Rechnung von heute nacht ;-)