Kongruenzlösung lösen in ganzen Zahlen

Question

Hallo zusammen.

Ich hatte hier so eine Minuaufgabe im Vorlesungsbuch zur Algebra und ich habe die echt unterschätzt. Die Aufgabe war es alle ganzzahligen Paare (x,y) zu finden, welche die lineare Gleichung 7x+3y = 5 lösen. D.h. in anderen Worten: Wir wollen alle Elemente der Menge {(x,y) ∈ Z^2 : 7x+3y = 5} =: U bestimmen.

Meine Idee:

In den rationalen Zahlen ist die Gleichung äquivalent zu y = (5-7x)/3. Da wir ganzzahlige x,y finden sollen, müssen wir uns fragen für welche x das y ganzzahlig ist. Das ist genau dann der Fall wenn 3 den Ausdruck (5-7x) teilt. Also äquivalent 5 kongruent 7x (mod 3) und das ist weiter äquivalent zu der Kongruenzgleichung

7x kongruent 2 (mod 3)

Man kann ja zuerst auch 7x kongruent 1 (mod 3) lösen und dann mit 2 die Lösung multiplizieren.

Wie löst man aber die Kongruenzgleichung? (Habe mich noch nie so richtig mit dem Lösen von Kongruenzen beschäftigt, sondern eher mit der Theorie…)

Also das eine Lösung existiert, ist klar, denn ggT(7,3) = 1. Wie bestimmt man die aber?

Answer 1

Betrachte die Gleichung 7x+3y = 5  nach dem Modul 3:

7x+3y≡ 5 mod 3

Wegen

7x≡ x mod 3

3y≡ 0 mod 3

5≡ 2 mod 3

vereinfacht sich 7x+3y≡ 5 mod 3 zu

x≡ 2 mod 3,

also x= 3n+2.

Eingesetzt in 7x+3y = 5:

7(3n+2)+3y = 5

3y=5-21n -14

3y=-9-21n

y=-3-7n.

Damit gilt (x,y)=(3n+2, -3-7n).

(Schreibfehler ausgebessert)

Comments

Dankeschön! :)

---

Sollte es am Ende nicht -1n sein?

---

Nee, -7n sollte es sein

Answer 2

Aus

\(7x\equiv 2 \mod 3\) folgt \(x\equiv 2\mod 3\), weil \(7\equiv 1\mod 3\).

Ansonsten würde man die Gleichung mit dem Inversen von \(7\mod 3\) multiplizieren.

Comments

Danke sehr! Nun kann man also daraus erkennen das

{(x,y) ∈ Z^2 : 7x+3y = 5} = {3n+2 : n ∈ |N_0}

U {-3n-1 : n ∈ |N_0} ist

---

Über die Darstellung der Menge würde ich noch einmal nachdenken.

---

Man kann es ja auch direkt als

{3n+2 : n ∈ Z} schreiben

---

Diese Menge soll jetzt was angeben?

---

Stimmt hast Recht

{(3n+2, y(3n+2)) : n ganz}

ist die richtige Menge. Habe das y vergessen :)

---

Ist das dieselbe Lösung, wie Du die zuvor von Abakus quittiert hast?

Wie ist Drine Menge zu verstehen: n ist erklärt, aber wie steht mit y?