Wie brrechne ich den Rest bei Potenzen?

Question

Aufgabe:

Wie rechne ich den Rest bei 10¹²²:7 aus?

Müsste man da mit Kongruenzen arbeiten?

Comments

Verwende 10¹²² ≡ 3¹²² mod 7 , sowie 3⁶ ≡ 1 mod 7.

Answer 1

Da

3^6 ≡ 1 mod 7

gilt

10^122 ≡ 3^{20·6 + 2} ≡ 3^2 ≡ 9 ≡ 2 mod 7