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?
210≡1 mod 11 Kleiner Satz von Fermat
Potenzieren mit 103
21030≡1 mod 11
Multiplizieren mit 23
21033≡8 mod 11
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 23 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
Na, 2^5 = 32 = -1 mod 11 und daher 2^10 = (-1)^2 = 1 mod 11 macht daraus eine Kopfrechenaufgabe.
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.
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
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos