Kongruenz beispielaufgabe mod

Question

Aufgabe:

7^x ≡ 10 mod 31

Bestimme x ohne Taschenrechner

Kann mir hier bitte jemand helfen?

Answer 1

Berechne der Reihe nach die Reste von 7^x bei Teilung durch 31.

Spätestens im 31. Versuch hast du einen Treffer (Rest 10).

Ich fange mal an.

7^1≡ 7 mod 31

7^2≡ 49 ≡ -13 mod 31

7^3≡ 343 ≡ 2 mod 31

7^4≡7^3·7  ≡ 2·7 ≡ 14 mod 31

Mache einfach weiter.

Comments

Gibt es dafür keinen schnelleren weg als bis zum 31. versuch zu rechnen?

---

Und wie kamst du auf -13?

---

Es müsste schon sehr unglücklich zugehen, wenn du erst im 31. Versuch fündig würdest.

Die Wahrscheinlichkeit, schon bis zu 16. Versuch einen Treffer zu landen, ist größer als 0,5.

In der Zeit, in der du deine Rückfrage "kein schnellerer Weg?" getippt hast, hättest du schon die vier nächsten Möglichkeiten berechnent.

---

Und wie kamst du auf -13?

Es gilt 49=1*31+18.

Es gilt auch 49=2*31-13.

Damit gilt sowohl

49 ≡ 18 mod 31

als auch

49 ≡ -13 mod 31.