Lösung der Gleichung a² ≡ 3 mod 109. Hinweis: 121 = 12 + 109.

Question

Wenn Pinocchio eine Email von Malvina bekommen hat, dass 121 = 12 + 109 ist, war er sehr verwundert. Finden Sie eine Lösung der Gleichung \( a^2 \equiv 3 \mod 109 \).

Comments

So eine Modolu-Aufgabe habe ich noch nie gesehen. Ich freu' mich schon auf die Antworten. Laut WolframAlpha sind die Lösungen:

a=49

a=60

---

Vom Duplikat:

Titel: Lösung einer Modulo Aufgabe a^2 ≡ 3 (mod 109)

Stichworte: modulo,zahlen,gleichung,mengen,elemente

a² ≡ 3 (mod 109)

Ich weiss, dass der Rest von 3 geteilt durch 109 3 ist. Ich habe versucht die Aufgabe oben mit der Formel aⁿ = (a+k • m)ⁿ   Weiss aber nicht ob das richtig wäre... bei mir kam a= a+ 327 raus, was schätze ich mal falsch ist:/

Sinn der Aufgabe ist es 121= 12+109 zu beweisen in dem man die Lösung für die Aufgabe oben berechnet.

Hat da jemand eine Lösung und will mir behilflich sein??

Answer 1

Hallo Troppelmann,

Die E-Mail von Malvina enthält einen wichtigen Hinweis; nämlich: $$11^2 \equiv 12 \mod 109$$

Nehme ich die Gleichung $$a^2 \equiv 3 \mod 109$$ und multipliziere diese mit \(4\), so erhält man: $$(2a)^2 \equiv 12 \mod 109$$ und zusammen mit dem Hinweis von oben folgt daraus: $$2a \equiv 11 \mod 109 \qquad (2)$$ so jetzt müssen wir noch 'durch-2-teilen', heißt in diesem Kontext mit der multiplikativen Inversen von \(2 \mod 109 \) multiplizieren. Wir suchen also eine Zahl \(z\), die mit \(2\) multipliziert, \(1\) ergibt: \(2 \cdot z \equiv 1 \mod 109\) Wenn man nicht gleich sieht, dass es \(55\) ist, hilft der erweiterte euklidische Algorithmus: $$\begin{array}{ccc|cc} a & b & q & s & t \\ \hline 109 & 2 & 54 & 1 & \colorbox{#ffff00}{-54} \\ 2 & 1 & 2 & 0 & 1 \\ 1 & 0& & 1 & 0\end{array}$$ Die Lösung ist \(z = 55 \equiv -54 \mod 109\). Multiplikation der Gleichung (2) mit \(55\) gibt: $$a_1 \equiv 11 \cdot 55 \equiv 60 \mod 109$$ Und da \(a\) quadriert wird, ist auch der negative Wert eine Lösung: $$a_2 \equiv -60 \equiv 49 \mod 109$$  (mache die Probe!)

Gruß Werner