Quadratische Kongruenz lösen

Question

Aufgabe:

Man untersuche die Kongruenz 14x² + 5x + 1 = 0 mod 98 auf Lösbarkeit.

Problem/Ansatz:

Hallo zusammen,

ich habe Probleme bei der Vorgehensweise. Ich habe die Vorgehensweise für quadratische Kongruenzen leider noch nicht verstanden. Ich würde mich sehr über Anregungen und Tipps bzw. einen Leitfaden für die Lösung solcher Aufgaben freuen!

Answer 1

Hallo,

Willkommen in der Mathelounge!

Ich bin zwar kein Profi in Zahlentheorie, ich mach' das eher als Amateur, aber ich weiß, dass wenn eine Lösung für$$14x^2+5x+1 \equiv_{98} 0$$existiert, dann muss es auch wegen $98= 2 \cdot 7^2$ jeweils mindestens eine Lösung für $$14x^2+5x+1 \equiv_{2} 0 \\ 14x^2+5x+1 \equiv_{7} 0$$geben. Da $14=2\cdot7$ ist, ist das recht einfach festzustellen. Es ist $$x\equiv_{2} 1 \\ x\equiv_{7} 4$$Falls Du da Probleme hast, frage bitte nach.

Die kleinste Zahl $x$ mit Rest $1$ bei Division durch $2$ und Rest $4$ bei Division durch $7$ ist $11$. Jetzt kannst Du z.B. mal die Zahlen $$x = 11 + k\cdot 14 \quad k=0,\,1,\,2,\, 3\dots$$probieren. Dann kommst Du schnell auf eine Lösung.

Gruß Werner

Comments

Wo kommen solche Gleichungen vor?

Wozu braucht man modulo-Lösungen statt der üblichen?

---

Hallo nochmal,

ich habe tatsächlich noch eine Frage: Könnte man 98 auch als 14 * 7 darstellen? Bzw. wieso ist 2 * 7² sinnvoller?

Vielen Dank für die wirklich sehr hilfreiche Erklärung!

---

Das ist eine Übungsaufgabe aus der Uni, Studiengang: Lehramt

---

Könnte man 98 auch als 14 * 7 darstellen?

Ja natürlich. Nur desto kleiner ein einzelner Teiler ist, umso einfacher kommst Du zu einer Lösung. Ich habe die Teiler $2$ und $7$ gennutzt.

Mit $\mod 14$ kommst Du zu$$\begin{aligned} 14x^2 + 5x + 1 &\equiv_{14} 0 \\5x + 1 &\equiv_{14} 0 \\ 5x &\equiv_{14} 13 \\\end{aligned}$$Hier muss man nun die multiplikative Inverse zu $5 \mod 14$ heraus bekommen. Das ist $3$ - also multipliziere die Gleichung mit $3$. $$\implies x \equiv_{14} 11$$ usw. das geht natürlich genauso.

---

.. Die Lösung aus $14x^2+5x+1 \equiv_{7}0$ kannst Du jetzt nicht mehr verwenden, da $7$ Teiler von $14$ ist. Der nächste Schritt wäre also wieder$$x := 11 + 14k$$ zu probieren - wie vorher auch.

---

Ich habe es mal versucht und komme zum Entschluss, dass die Kongruenz für x=11,25,39,53,67,... lösbar ist. Kann das stimmen?

---

... dass die Kongruenz für x=11,25,39,53,67,... lösbar ist. Kann das stimmen?

Nö - nur für $x=53= 11 + 14 \cdot 3$. Z. B. bei $11$ kommt doch raus:$$\begin{aligned} (14 \cdot 11 + 5) \cdot 11 + 1 &\equiv_{98} 159 \cdot 11 + 1\\ &\equiv_{98} 61 \cdot 11 + 1 \\ &\equiv_{98} 671 + 1 \\&\equiv_{98} 83 + 1\\ &\equiv_{98} 84 \not\equiv_{98} 0 \end{aligned}$$es gibt nur genau die eine Lösung.

---

Ahh, verstehe! Vielen Dank!! Ich verstehe nur noch eine Sache nicht. Wie komme ich von

14x²+5x+1=0 mod 2

auf

x=1 mod 2

?

Also, welche Rechenschritte werden da genau durchgeführt.

---

Steht doch alles in der Antwort. Es ist $14 \equiv 0 \mod 2$ etc. Es vereinfacht sich doch alles.

---

Wie komme ich von
14x²+5x+1=0 mod 2
auf
x=1 mod 2

Dass $2\cdot k \equiv 0 \mod 2$ ist, mit $k\in\mathbb{Z}$, sollte Dir klar sein. Und im Detail geht es in diesem Fall so:$$\begin{aligned}14x^2 + 5x + 1 &\equiv_2 0 \\ \underbrace{2\cdot(7x^2)}_{\equiv_2 \,0} + \underbrace{2\cdot(2x)}_{\equiv_2\,0} + x + 1 &\equiv_2 0\\ x+1&\equiv_2 0 &&|\, +1\\ x+\underbrace{2}_{\equiv_2\,0}&\equiv_2 1\\ x &\equiv_2 1\end{aligned}$$