Rest rechnen mit hohen Potenzen: Bsp: Rest (3^{57}, 17) =?

Question

Aloha-olah. Heißt "Hallo" und "Auf Wiedersehen" in Hawaii. Aber das hat nichts mit der folgenden Aufgabe zu tun, um die es jetzt geht

Berechne Rest (3⁵⁷, 17).

Das Endergebnis ist laut Python-Rechner 14.

Ansatz wäre bisher

Rest ( (3³)¹⁹, 17).

Wir wissen nicht, wie das berechnet wird, bzw. welche Regeln man am geschicktesten anwendet.

Liebe Grüße,

Marceline The Vampire Queen

Comments

Tipp: Berechne mal mit deinem Rechner

Rest (3^{40}, 17) und Rest (3^{41}, 17).

Answer 1

Nach dem kleinen fermatschen Satz ist 3⁵⁷ ≡ 3^16·3+9 ≡ 3⁹ ≡ 14 mod 17.

Comments

Wie erkennt man allerdings schnell das 3^16 mod 17 = 1 ist ?

Über eine Wertetabelle hätte ich 3^8 mod 17 = -1 zuerst gefunden.

Gibt es da einen Trick sowas noch schneller zu erkennen?

---

Das gilt nach besagtem Satz.

---

Achja. Danke.

a^(p - 1) mod p = 1 (https://de.wikipedia.org/wiki/Kleiner_fermatscher_Satz)

---

Und wie geht die Rest(9²⁷ , 55) ? da komme ich leider nicht weiter..

---

Was natürlich geht allerdings sehr zeitaufwenig ist ist das runterbrechen auf einzelne Faktoren

9^27 mod 55
= 9·9^26 mod 55
= 9·81^13 mod 55
= 9·26^13 mod 55
= 9·26·26^12 mod 55
= 9·26·676^6 mod 55
= 9·26·16^6 mod 55
= 9·26·256^3 mod 55
= 9·26·36^3 mod 55
= 9·26·36·36^2 mod 55
= 9·26·36·1296 mod 55
= 9·26·36·31 mod 55
= 234·1116 mod 55
= 14·16 mod 55
= 224 mod 55
4

Ich hoffe aber Spacko hat auch hier einen geschickteren Ansatz.

---

Und wie geht die Rest(9²⁷ , 55) ? da komme ich leider nicht weiter..

Betrachte den Rest mod 5 ( der ist -1) und den Rest mod 11.

Da $$9\equiv\; -2\; mod \;11$$

gilt, ist

$$9^5\equiv\; (-2)^5\; \equiv\;(-32)\equiv\;1 \;mod \;11$$

Damit solltest du auf kurzen Wege zum Rest von

$$9^{25} \;mod \;11$$ kommen und den Schritt bis $$9^{27} $$ auch noch schaffen. 

---

Warum darf man das genau so machen

22 mod 11 = 0

22 mod 5 = 2

22 mod 55 = 22

Weißt du da etwas wo ich die Grundlagen nachlesen kann?

---

Weißt du da etwas wo ich die Grundlagen nachlesen kann?

Mist.

Ich wollte gerade die Broschüre "Korrespondenzzirkel Mathematik - Arbeitsmaterial für Klasse 7" hochladen, aber pdf-Dateien werden als Anhang nicht akzeptiert.

Deshalb hier nur ein Screenshot der Seite 15:

---

Danke für die Antworten.

@Der Mathe_coach: Ich verstehe eine Umschreibung nicht:

= 9·81¹³ mod 55
= 9·26¹³ mod 55

81¹³ und 26¹³ sind doch nicht gleich.

@ abakus: Wie kommst du auf 22? Ich verstehe dass du 55 aufsplittest auf 5 und 11. Aber warum

9 = - 2 mod 11 ?

Wir müssen die Aufgaben ohne Taschenrechner rechnen. Also können nicht mal eben so 9³ berechnen, ohne es umzuformen.

---

@Der Mathe_coach: Ich verstehe eine Umschreibung nicht:

a^b mod m = (a mod m)^b mod m

Du kannst den Modulo also bereits auf alle Faktoren anwenden.

@ abakus: Wie kommst du auf 22? Ich verstehe dass du 55 aufsplittest auf 5 und 11. Aber warum

9 ≡ -2 mod 11 weil
-2 + 11 = 9

Der Rest 9 ist also auch Gleichbedeutend mit einem Rest von -2. Wenn ich nämlich einmal 11 mehr subtrahiere.

---

Deshalb hier nur ein Screenshot der Seite 15

Vielen lieben Dank erstmal dafür. Die Sätze darauf kannte ich bereits.

Ich muss mir da mal Gedanken drüber machen wie ich aus dem Modula von a und dem Modulo von b mir den Modulo von a*b herausbekomme.

Das hat ja offensichtlich mit dieser Zeile zu tun.

Ich werde da morgen mal drüber nachdenken.

Answer 2

Das sind keine hohen, sondern winzige Potenzen.

Ein einfachen Algorithmus aus 3 Zeilen für diese Pow-Mod-Funktion findet man unter

http://www.gerdlamprecht.de/Roemisch_JAVA.htm Beispiel 122

Nach 5 Schritten ist b<1 und das Ergebnis in b=aC[d+1]=aC[d]%c; also 14.

Das kann man noch weiter steigern und sich die PowPowMod(x,y,z,h) unter

http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php 

mit richtig großen Zahlen ausrechnen lassen. (suche Funktion PowPowMod )