8 hoch 43 mod 85 ohne Taschenrechner?
Wie berechne das ohne Taschenrechner ?
4 Antworten
Als Methode, die man stur geradeaus anwenden kann, (Algorithmus) würde ich das übliche Verfahren zur Berechnung von Potenzen mit natürlichem Exponenten nehmen und bei jedem Schritt die Reste zu 85 der Größen berechnen, die addiert oder multipliziert werden:
8^43
b=8, e=43, x=1 (momentane Basis, momentaner Exponent, momentanes Ergebnis)
(Das Endergebnis ist nach jedem Schritt x × b^e - wenn e=0 ist, ist x das Endergebnis und wir sind fertig)
43 ist ungerade => x durch x×8 ersetzen und e durch e-1: x=8 , e=42
x < 85, also keine Restberechnung nötig
42÷2=21, 8×8=64 => b durch b×b und e durch e÷2 ersetzen: b=64, e=21
21 ist ungerade ...
x=8×64=512, e=10, b=64×64
6×85=510, also x durch 512-510 ersetzen
64×64 ist 2^12=4096, das weiß ich zwar auswendig, aber nur, weil ich mich viel mit dem "Motorraum" von Computern beschäftigt habe.
Deshalb besser: 64=2^6, also 64 6-mal verdoppeln (und immer Rest 85 nehmen)
erste Verdoppelung: 128; kongruent 43 (85)
zweite: 86; kongruent 1
dritte: 2
vierte, fünfte, sechste: 16
x=2, b=16, e=10
10 ist gerade, x bleibt
b durch b×b und e durch e÷2 ersetzen:
x=2, b=256, e=5
3×85=255, also b kongruent 1
Damit sind wir fertig, weil weder b noch x sich jetzt noch ändern können (sie können ja nur mit b multipliziert werden). Ich mach trotzdem weiter:
5 ist ungerade => x durch x×b und e durch e-1 ersetzen: x=2, b=1, e=4
e durch e÷2 und b durch b×b ersetzen: b=1, e=2
2 ist gerade => x und e bleiben
e durch e÷2 und b durch b×b ersetzen: b=1, e=1
1 ist ungerade => x durch x×b und e durch e-1 ersetzen: x=2, b=1, e=0
bei e=0 sind wir fertig
Also: 8^43 kongruent 2 modulo 85
Im folgenden habe ich mal ein paar Lösungswege aufgeschrieben, wie man das (möglichst ohne Taschenrechner) rechnen kann.
============
Zunächst einmal kann man die Primfaktorzerlegung von 85 finden...
85 = 5 ⋅ 17
Damit kann man dann
φ(85) = φ(5 ⋅ 17) = φ(5) ⋅ φ(17) = 4 ⋅ 16 = 64
berechnen.
Außerdem sind 8 und 85 offensichtlich teilerfremd. Bzw. sind auch 2 und 85 teilerfremd.
Nach Satz von Euler ist nun
8⁶⁴ ≡ 1 mod 85
bzw.
2⁶⁴ ≡ 1 mod 85,
so dass man quasi im Exponenten modulo 64 rechnen kann.
Ergebnis: 8⁴³ mod 85 = 2
============
Alternativ könnte man mit dem chinesischen Restsatz die Kongruenzgleichung x ≡ 8⁴³ mod 85 in die beiden Kongruenzgleichungen x ≡ 8⁴³ mod 5 und x ≡ 8⁴³ mod 17 aufteilen, und dann den kleinen Satz von Fermat ausnutzen.
============
Ansonsten könnte man auch mit einer Square-and-multiply-Methode arbeiten.
https://de.wikipedia.org/wiki/Binäre_Exponentiation
Im konkreten Fall kann das dann so aussehen...
Das ist aber von Hand trotzdem noch eher aufwändig.
============
Bzw. könnte man auch einfach so lange weiter mit 8 multiplizieren und modulo 85 reduzieren, bis man etwas Einfaches erhält...
Ich würde erstmal 8^3 berechnen (512) und dann 512 mod 85 (=2). Dann nutzt du:
8^43 = 8 * 8^42 = 8 * (8^3)^14
Wenn du nun mod 85 rechnest:
8 * (8^3)^14 mod 85
= 8 * 2^14 mod 85
= 2^17 mod 85
= 2^9 * 2^8 mod 85
= 2 * 2^8 mod 85
= 2^9 mod 85
= 2
da 2^9 = 512.
Du brauchst nur 8^3 mod 85, das ist 2.
Wie kommt hoch 3 zustande ? Und wie rechnest du das weiter ?
8^3 berechnen (512) und dann 512 mod 85 (=2), der erste Teil reicht mir ja schon, wenn ich auf die 2 komme :) Warum 8 hoch 3 ?