Bestimmen aller ganzzahligen Lösungen (Kongruenz, Modulo, elementare Zahlentheorie)

Question

Aufgabe: Bestimmen aller ganzzahligen Lösungen

x²+3x−4 ≡ 0 (mod 125)

Problem/Ansatz:

man kann dies ja auch anschreiben als (x-1,5)²-6,25. Nun stellt sich heraus, dass die Kongruenz äquivalent zu (x-1,5)² ≡ 6,25 mod (125) ist.

So weit bin ich gekommen, allerdings weiß ich nicht genau, wie ich weiter vorgehen soll - jetzt müsste ich vermutlich prüfen, ob 6,25 ein quadratischer Rest von mod125 ist ... kann mir da bitte jemand weiterhelfen? :(

Answer 1

x²+3x−4 lässt sich faktorisieren zu (x+4)(x-1).

Ein Produkt zweier Faktoren ist durch 125 teilbar, wenn einer der Faktoren durch 125 teilbar ist oder einer durch 5 und der andere durch 25 teilbar ist.

Ist einer der beiden Faktoren (x+4) und (x-1) durch 5 teilbar, ist es der andere auch, denn sie unterscheiden sich um 5. Somit muss gelten

(x+4)≡ 0 (mod 25) oder (x-1)≡ 0 (mod 25)

Die Lösungen sind somit

x≡ -4 (mod 25) und x≡ 1 (mod 25).

Zwischen 0 und 125 gibt es beispielsweise die Lösungen 1, 21, 26, 46, 51, 71, 76, 96, 101 und 121.

Comments

Tausend Dank! So einfach & ich denk immer kompliziert. Danke vielmals!

Answer 2

Hier mit Dezimalzahlen zu hantieren, ist gänzlich unangebracht.

Wir haben$$x^2+3x-4\equiv 0 (125)\iff x^2-122x\equiv 4 (125) \iff \\(x-61)^2\equiv 3725\equiv 10^2 (125)\iff x-61\equiv \pm 10 (125)\iff \\x\equiv 51 \vee x \equiv 71 (125)$$

Comments

x=46 ist auch eine Lösung der gegebenen Kongruenz.

Ich grüble gerade, an welcher Stelle du die verloren hast.

---

Hallo abakus,

da habe ich nicht aufgepasst; denn \(x^2\equiv 100 (125)\) hat mehr als

2 Lösungen im Restklassenring; denn 125 ist keine Primzahl.

Vielen Dank für deinen Kommentar.

---

Um auch das zum Ende zu bringen: aus \(x^2\equiv 100 (125)\) folgt

\(x^2\equiv \red{100}  \equiv \red{225}\equiv 350\equiv 475\cdots \equiv \red{1225} \cdots \equiv \red{1600}(125) \equiv \red{3600}(125) \equiv \red{4225}(125)\)