0 Daumen
195 Aufrufe

Aufgabe:

7^x ≡ 10 mod 31

Bestimme x ohne Taschenrechner


Kann mir hier bitte jemand helfen?

Avatar von

1 Antwort

0 Daumen

Berechne der Reihe nach die Reste von 7x 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.

Avatar von 53 k 🚀

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community