Prüfen Sie die Lösbarkeit der Kongruenz x2 + 97x ≡ 3 mod 101 in Z:

Question

Überprüfen Sie die Lösbarkeit der Kongruenz x² + 97x ≡ 3 mod 101 in Z:

(Tipp: Binomische Formel)

Comments

Modulo 101 gilt

$$ x^2 +97x-3 \equiv x^2-4x-3 \equiv (\underbrace{x-a}_{=: y})^2 -b \mod (101) $$

mit geeigneten a,b. Die Lösbarkeit reduziert sich also auf die Lösbarkeit von:

$$ y^2 \equiv b \mod (101) $$

Du musst also nur entscheiden ob b ein Quadrat modulo 101 ist oder nicht.

---

also ich wollte gerne noch mal auf den Kommentar eingehen...^^

Also hätten wir dann (x-2)² + 7 mod (101), da x²-4x-3 = (x-2)² -7 = x²-4x+4-7.

Damit ist (\( \frac{7}{101} \)) = (-1)^ \( \frac{7-1}{2} \)*\( \frac{101-1}{2} \)*(\( \frac{101}{7} \))

= (\( \frac{3}{7} \)) = (\( \frac{-4}{7} \)) = (\( \frac{-1}{7} \)) (\( \frac{2}{7} \))(\( \frac{2}{7} \))

= (-1)*1*1 = -1, also keine Lösbarkeit für die Kongruenz!^^

Sry wegen dem Format, ich weiss es leider nicht besser, aber ich hoffe du kannst sehen, das ich das Legendre-Symbol verwendet habe.^^

---

(x-2)^2 - 7 mod (101),

Vermutlich nur ein Tippfehler, aber der Rest ist richtig.

---

Eigentlich schon (+), da ja -b = - (-7) = +7 - dann habe ich etwas nicht ganz verstanden...^^

---

x^2-4x-3 = (x-2)^2 -7

Ist korrekt. Jetzt identifizieren:

(x-a)^2 - b

=> a=2 und b=7

Answer 1

x² + 97x ≡ 3 mod 101

4(x² + 97x )≡ 12 mod 101

4x2+388x+9409≡9421 mod 101

(4x+97)²≡9421 mod 101

9421 und 101 sind Primzahlen.

Vermutlich gibt es einen Satz:

Für Primzahlen p≠q ist die Kongruenz a²≡p mod q nicht lösbar.

Comments

Für Primzahlen p≠q ist die Kongruenz a2≡p mod q nicht lösbar.

Gegenbeispiele:$$\begin{aligned}12^2 &\equiv 43 \mod 101\\ 15^2 &\equiv 23 \mod 101\end{aligned}$$hier gibt's aber trotzdem keine Lösung$$\begin{aligned} x^2+97 x&\equiv 3\mod 101 &&|\, - 101x \equiv 0\\x^2 - 4x &\equiv 3 &&|\,+4 \\x^2 - 4x + 4 &\equiv 7\\(x-2)^2 &\equiv 7\\ \mathbb L &= \{\}\end{aligned}$$die \(7\) ist kein quadratischer Rest bezüglich des Moduls \(101\). Also hat die Gleichung keine Lösung.