Ermittle den Rest von 12^1337 bei der Division mit 11?

Kann mir dabei wer helfen? Mir geht es vor allem um das vorgehen und die Logik dahinter weniger um das Ergebnis
Danke im Voraus

Answer 1

[Mathmaninoff, UserMod Light]

Normalerweise wendet man für so etwas den kleinen fermatschen Satz aᵖ⁻¹ ≡ 1 (mod p) an.

In diesem Fall ist es sogar noch einfacher, weil bereits 12 ≡ 1 (mod 11). Wenn ich zwei Zahlen multipliziere, die den Rest 1 haben, hat das Produkt immer noch Rest 1, denn (11a + 1)(11b + 1) = 121ab + 11a + 11b + 1 = 11(11ab + a + b) + 1.

Eine Potenz ist eine wiederholte Multiplikation, d.h. 12ⁿ = 12 ⋅ 12ⁿ⁻¹. Wenn 12 den Rest 1 hat, dann haben induktiv alle Potenzen von 12 den Rest 1.