0 Daumen
439 Aufrufe

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

(Tipp: Binomische Formel)

Avatar von

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...^^

(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

1 Antwort

0 Daumen

x2 + 97x ≡ 3 mod 101

4(x2 + 97x )≡ 12 mod 101

4x2+388x+9409≡9421 mod 101

(4x+97)2≡9421 mod 101

9421 und 101 sind Primzahlen.

Vermutlich gibt es einen Satz:

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

Avatar von 123 k 🚀
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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community