0 Daumen
2,4k Aufrufe

Aufgabe:

ddddd.png


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?

Avatar von

3 Antworten

+3 Daumen
 
Beste Antwort

210≡1 mod 11 Kleiner Satz von Fermat

Potenzieren mit 103

21030≡1 mod 11

Multiplizieren mit 23

21033≡8 mod 11

Avatar von 123 k 🚀

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 :


eeeee.png

das p = die 11 oder die 1033?

Und wie kommt man im letzten Schritt von kongruent zu 1 mod 11 durch die 2zu 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

+2 Daumen

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

Avatar von 26 k

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.

+2 Daumen

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

Avatar von 477 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community