Modulo Gleichung mit grossem Exponenten 77^{17} ≡ z (mod 19)

Question

Aufgabe:

Finde eine Zahl z ∈ ℕ mit z ≤ 19, so dass gilt

77¹⁷ ≡ z  (mod 19)

Problem/Ansatz:

Ich komm nicht' in die Puschen. Normalerweise ist eine Modulo Gleichung ja so definiert, dass auf der linken Seite die Zahl steht, welche das Produkt von der Zahl in der Modulo-Klammer mit einem unbekannten Faktor, darstelt wobei z dann den Rest darstellt. z.B. gilt 4127 = 2 mod (11), weil 375* 11 = 4125, sind Rest 2 zur 4127.

Aber hier steht jetzt eine sehr hohe Potenz, nämlich 77¹⁷. Die Aufgabe stammt aus einer Klausur vom 6.April 2018, in der kein Taschenrechner zugelassen war.

Answer 1

77 ≡ 1 (mod 19)

also ist das

1^17  ≡ z  (mod 19)

also z=1