Kleiner Satz von Fermat

Wissenschaft Mathematik
#1

Hallo zusammen,

momentan habe ich ein paar Probleme mit dem kleinen Satz von Fermat.

Ich möchte den anwenden, um z. B. folgendes zu berechnen.

47^162 mod 11

und

2^2705 mod 2707 (2707 ist eine Primzahl).

Eigentlich hatte ich gedacht, dass ich den Satz verstanden habe und ihn anwenden kann. Wenn der Exponent den Faktor (p-1) enthält habe ich auch kein Problem damit, aber bei Rechnungen wie oben, stehe ich momentan voll auf der Leitung.

Kann mit bitte jemand anhand der Beispiele oben beschreiben, wie ich das berechnen kann?

Danke!

powerblue

#2

hi,

47^162 mod 11

jetzt bin ích mir insgesamt sehr unsicher, denn ich hab mit dem kleinen fermat und restklassen schon sehr lange nix mehr zu tun gehabt, aber folgende überlegungen müssten doch stimmen… (und wenn nicht, kann ich was lernen, wenn mir wer den fehler zeigt):

47^162 mod 11 = (4 * 11 + 3)^162 mod 11 = 3^162 mod 11

3^162 = 3^154 * 3^8´
3^154 = 3^(11*14) = (3^11)^14

fermat:
3^11 = 3 mod 11

3^154 mod 11 = 3^14 mod 11

also:

47^162 mod 11 = 3^14 mod 11 * 3^8´ mod 11 = 3^22 mod 11 =
= (3^11)^2 mod 11´= 9 mod 11 = 9

???

m.

#3

CAS bestätigt.
Hallo Michael.

47^162 mod 11 = … = 9

Ich habe die Zwischenschritte nicht nachgerechnet, aber laut CAS stimmt das Ergebnis. :smile:

Liebe Grüße,

TN

#4

Wegen 11 und 47 bzw. 3 teilerfremd ist sogar

47^10=1 mod 11 bzw. 3^10=1 mod 11

damit

47^162=(3^10)^16*3^2=9 mod 11

Gruß, Lutz

#5

Danke
Hallo zusammen,

Danke für die Antworten, habe es jetzt verstanden.

Grüße

powerblue