Question

Bestimmen Sie \( 13^{57} \) modulo 11.

Da kommt 7 raus, aber wie kommt man darauf?

Answer 1

Falls ihr den kleinen Fermat noch nicht hattet:

Da \(2^5 = 32\equiv_{11}-1\) gilt, haben wir

$$13^{57}\equiv_{11}2^{5\cdot 11 + 2}\equiv_{11}(-1)^{11}\cdot 4 \equiv_{11}7$$

Answer 2

Kleiner Satz von Fermat.

13¹⁰≡1 mod 11

Das Ganze hoch 5:

13⁵⁰≡1 mod 11

Jetzt brauchen wir noch 13⁷:

Es gilt 13≡2 mod 11

Daraus folgt 13⁷≡2⁷ mod 11, also 13⁷≡128≡7 mod 11,

13⁵⁰·13⁷≡1·7≡7 mod 11

Answer 3

Alle Reste bei Division durch 11 lassen sich als alternierende Quersumme berechnen.

13¹⁰≡1 mod11   Potenzieren mit 5

13⁵⁰≡1 mod11

13⁷ ≡7 mod11   Multiplizieren

13⁵⁰⁺⁷≡7 mod11