Question

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.

Answer 1

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

Comments

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

Answer 2

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:

32²⁴ Ξ 1 mod 35

32⁷² Ξ 32^3*24 Ξ (32²⁴)³ Ξ 1³ Ξ 1 mod 35

Das Ergebnis ist ebenfalls 1.

Gruß