0 Daumen
2,2k Aufrufe
Welcher Rest lässt 32^{72} bei der Division durch 35?

Ich bin wie folgt vorgegangen:

Kleiner Satz von Fermat:
ggt(35,32) über Euklid ermittelt =1

Φ(35) berechnet = 24

Der Satz von Fermat sagt, dass

32^{24} = 1 mod 35

--> 32^{48} = 1 mod 35

32^{2} = 9 mod 35
32^{4} = 11 mod 35
32^{8} = ???
32^{16} = ???

Die Modulo Rechnungen mit dem höhren Potenzen spuckt der Taschenrechner nichtmher aus also Frag ich
mich wie ich an dieser Stelle jetzt weiter rechnen muss.
Avatar von

2 Antworten

+1 Daumen

32^72 mod 35

= (-3)^72 mod 35

= (9)^36 mod 35

= (81)^18 mod 35

= (11)^18 mod 35

= (121)^9 mod 35

= (16)^9 mod 35

= 16 * (16)^8 mod 35

= 16 * (256)^4 mod 35

= 16 * (11)^4 mod 35

= 16 * (121)^2 mod 35

= 16 * (16)^2 mod 35

= 16 * 256 mod 35

= 16 * 11 mod 35

= 176 mod 35

= 1

Avatar von 486 k 🚀

Wenn du weißt das

32^24 = 1 mod 35 dann wäre das noch einfacher

32^72 = 32^{24 + 24 + 24} mod 35

32^72 = 32^24 * 32^24 * 32^24 mod 35

32^72 = 1 * 1 * 1 mod 35

32^72 = 1 mod 35

0 Daumen

Hi,

Die Antwort von Mathecoach beinhaltet ja schon eine Möglichkeit für die Berechnung des Rests. Ich möchte in meiner Antwort zusätzlich an deinem Ansatz anknüpfen.

Der Satz von Euler (Fermat beziehte sich meines Wissens nach nur auf Primzahlen, während Euler den Satz verallgemeinerte) liefert:

3224 Ξ 1 mod 35

3272 Ξ 323*24 Ξ (3224)Ξ 1Ξ 1 mod 35

Das Ergebnis ist ebenfalls 1.

Gruß

Avatar von 6,0 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community