Modulo mit Potenzen?
Wie zerlege ich 7^23 mod 143 ?
Ich komme leider nicht drauf, wie ich die 7^23 zerlege .. bitte um Hilfe.
4 Antworten
143 = 11 • 13
Zuerst für den Rest 11. Nach dem kleinen Satz von Fermat ist 7^(10) = 1 mod 11, also auch 7^20 = 1 mod 11 und damit bleibt nur 7³ zu berechnen. Es ist 7³ = (-4)³ mod 11 = -64 mod 11 = 2 mod 11.
Da für 13 auch 2 rauskommt, ist es hier sehr einfach und man hat
7^(23) = 2 mod 143
Für 13 ist 7^12 = 1 mod 13 nach dem kleinen Fermat, also auch 7^24. weil 2 • 7 = 14 = 1 mod 13, ist also 7^23 = 2 mod 13, noch als Ergänzung zu oben.
Du kannst - bei 1 beginnend - 23 mal {mit 7 multiplizieren und den 43-er Rest bilden.}
Besser verwendet man einen Algorithmus, mit dem man ganzzahlige Potenzen schneller berechnen kann:
Eingang Basis, Exponent (> 0)
Ergebnis <-- 1
solange Exponent > 0
falls Exponent ungerade
Ergebnis <-- Ergebnis * Basis
Exponent <-- Exponent - 1
Basis <-- Basis * Basis
Exponent <-- Exponent / 2
Ausgang Ergebnis
und ergänzt den Schritt
Ergebnis <-- Ergebnis * Basis
zu
Ergebnis <-- Ergebnis * Basis
Ergebnis <-- Ergebnis mod 143
sowie
Basis <-- Basis * Basis
zu
Basis <-- Basis * Basis
Basis <-- Basis mod 143
Ich habe es mit einem Java-Programm ausgerechnet, das nicht rundet (es nimmt genau deine Zahl). Das Ergenbnis ist:
11
Anmerkung zu dem fehlerhaften Ergebnis der Berechnung: Das liegt vermutlich daran, dass double für gewöhnlich 64 Bits verwendet (52 davon für die eigentlichen Ziffern), während für 7^23 mindestens 64.569163 (also 65) Bits benötigt werden (wäre dann wohl n Fall für nen java.math.BigInteger o.ä.).
Was gibts denn da groß zu "zerlegen"?
7^23 = 27368747340080916343
27368747340080916343 mod 143 = 2
P.S.: 7^23 <=> 7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7
wenn ich 7^23 in meinen Taschenrechner eingebe, dann komme ich
2.736874734 x10 ^19
... also irgendwas komischen. Wenn ich damit weiter rechne und /143 eingebe, dann bekomme ich 1.9138 ... x10 ^17
Okay, und warum rechnest du (7^23)/143 wenn du nach (7^23) mod 143 fragst?
P.S.: Was dein Taschenrechner anzeigt ist auf jeden Fall korrekt (das mit 2.736874734*10^19), er hat nur ein zu kleines Display um die komplette Zahl ohne weiteres anzuzeigen.
P.P.S.: x*10^y bedeutet nichts anderes als "verschiebe das Komma in x um y Stellen nach rechts".
*10^17 sind einfach 17 Nullen hinten dran... bzw Komma um 17 Stellen nach rechts
Okay, der Rechenweg:
Methode 1: Machs wie in der Grundschule, z.B. 5/2=2 Rest 1. Mit anderen Worten: 5 mod 2 = 1.
Methode 2: mod(x, y) = x - (int(x / y) * y)
In deinem Fall kommt noch ein weiterer Schritt dazu, der vor dem ganzen Ausgeführt wird: 7^23 = 27368747340080916343
Für Methode 1 also: 27368747340080916343/143 = 191389841539027387 Rest 2
P.S.: Wie gesagt, dürfte aber dein Taschenrechner mit der Verarbeitung dieser Zahlen Probleme haben (oder zumindest mit der Darstellung).
Dein Taschenrechner hat auch eine Modulo-Funktion. Die könntest du vlt einfach benutzen
Nur dass es nicht um 7E23=700000000000000000000000 sondern um 7^23=27368747340080916343 geht...
Ausserdem hat dein Programm offenbar noch ein weiteres Problem: 7E23 mod 143 = 15... Nicht 11...