Modulo ausrechnen große Zahlen. Bsp. (2^13)^17 mod 33

Question

das sind schon große Zahlen und deshalb kann das mein GTR nicht berechnen, daher wollt ich fragen, ob ihr da mir helfen könntet.

Einmal geht es um:

(2¹³)¹⁷ mod 33

Wenn ich alles richtig gemacht habe, müsste da 2 rauskommen.

8¹⁷ mod 33 soll 2 sein, wenn ich es richtig gemacht hab.

Und 27¹⁷ mod 33 soll 3 sein.

Passen meine Ergebnisse?

Comments

Wolframalpha kommt auch auf 2. https://www.wolframalpha.com/input/?i=(2%5E13)%5E17+mod+33 und deine andern Ergebnisse.

Wenn man deine Rechenschritte prüfen sollte, solltest du sie eigentlich hinschreiben.

Hier ein möglicher Rechenweg: https://www.mathelounge.de/101351/wie-rechne-ich-grosse-zahlen-modulo

Answer 1

Es ist offenbar \(2^5 = 32 \equiv -1 \mod 33\), also ist \(2^{10} = (2^5)^2 \equiv 1 \mod 33\). Dies ausgenutzt ergibt sich:

$$ \left(2^{13}\right)^{17} \equiv \left(2^{3}\right)^{17} = 2^{51} \equiv 2 \mod 33.$$Es kommt also – ganz ohne Taschenrechner, also im Kopf, gerechnet – tatsächlich 2 heraus. Deine Rechnung verstehe ich allerding nicht ganz.

Answer 2

(2^13)^17 mod 33

= 2^{13 * 17} mod 33

= 2^{221} mod 33

= 2 * 2^{220} mod 33

= 2 * (2^10)^22 mod 33

= 2 * (1024 mod 33)^22 mod 33

= 2 * 1^22 mod 33

= 2 * 1 mod 33

= 2

--------------------------------------------------

8^17 mod 33

= (2^3)^17 mod 33

= 2^51 mod 33

= 2 * 2^50 mod 33

= 2 * (2^10)^5 mod 33

= 2 * (1024 mod 33)^5 mod 33

= 2 * 1^5 mod 33

2

Comments

8^17 war wohl ein Zwischenergebnis aus der Bearbeitung der eigentlichen Aufgabe.

---

Ja, Allerdings habe ich seine Rechnung auch nicht wirklich verstanden.

Gehört 27^17 mod 33 denn zu dieser Aufgabe oder ist das eine andere?

---

Das ist der Teil, den ich nicht verstanden habe, falls er Teil der Rechnung gewesen sein sollte.