Modulo elf. Potenzrechnung mit Primzahl. 2^(1033) mod 11 =?

Question

Aufgabe:

Problem/Ansatz:

Wenn man keine Primzahl im Exponenten hat, kann man ihn ja ganz einfach aufdröseln bei 300 zum Beispiel dann schreiben 2*150 etc. aber was mache ich denn bei 1033 (Primzahl) wie rechne ich dann modulo aus?

Answer 1

2¹⁰≡1 mod 11 Kleiner Satz von Fermat

Potenzieren mit 103

2¹⁰³⁰≡1 mod 11

Multiplizieren mit 2³

2¹⁰³³≡8 mod 11

Comments

Dafür gebe ich einen Daumen.

https://de.wikipedia.org/wiki/Kleiner_fermatscher_Satz

Und ich habe heute dann auch gleich noch etwas aus der Zahlentheorie dazu gelernt.

---

Verstehe ich den kleinen fermatschen Satz richtig, man nimmt also für p = die zahl hinter modulo also die 11 anstelle der 1033?  bei wikipedia steht ja :

das p = die 11 oder die 1033?

---

Und wie kommt man im letzten Schritt von kongruent zu 1 mod 11 durch die 2³  zu kongruent zu 8 mod 11 ??

---

Das steht doch oben in der Antwort:

Multiplizieren mit 2^3

2^1030 ≡ 1 MOD 11

2^1030 * 2^3 ≡ 1 * 2^3 MOD 11

2^1033 ≡ 8 MOD 11

Answer 2

Na, 2^5 = 32 = -1 mod 11 und daher 2^10 = (-1)^2 = 1 mod 11 macht daraus eine Kopfrechenaufgabe.

Comments

Wie bist du denn darauf gekommen?

Also 32 =10 mod 11 bei mir wie kommst du da auf -1

---

Wegen 10-11=-1 kann man statt mit 10 mit der viel handlicheren -1 rechnen.

Answer 3

Theoretisch könntest du das auch wie folgt machen. Es ist aber zweckmäßiger wie es Gast az0815 gemacht hat zunächst Potenzen von 2 zu untersuchen. Das 32 eine Zweierpotenz ist darf man wissen.

2^1033 mod11

= 2 * 2^1032 mod 11

= 2 * 4^516 mod 11

= 2 * 16^258 mod 11

= 2 * 5^258 mod 11

= 2 * 25^129 mod 11

= 2 * 3^129 mod 11

= 2 * 3 * 3^128 mod 11

= 2 * 3 * 9^64 mod 11

= 2 * 3 * 81^32 mod 11

= 2 * 3 * 4^32 mod 11

= 2 * 3 * 16^16 mod 11

= 2 * 3 * 5^16 mod 11

= 2 * 3 * 25^8 mod 11

= 2 * 3 * 3^8 mod 11

= 2 * 3 * 9^4 mod 11

= 2 * 3 * 81^2 mod 11

= 2 * 3 * 4^2 mod 11

= 2 * 3 * 16 mod 11

= 2 * 3 * 5 mod 11

= 30 mod 11

= 8