Berechnen Sie alle Lösungen x ∈ ℤ des Kongruenzsystems

Question

Beispiel :
Berechnen Sie alle Lösungen x ∈ ℤ des Kongruenzsystems
x ≡ 6 mod 7,
x ≡ 9 mod 12,
x ≡ 11 mod 25.

Danke für die Antwort

Answer 1

Verwende den chinesischen Restsatz.

Comments

Hätte eine Frage, also 6,9,11 sind teilerfremd und deshalb kann ich den chinesischen Restsatz verwenden oder? Und wie kann ich bei dem erweiterten euklidischen Algorithmus vorgehen ?

---

Du kannst den chinesischen Restsatz verwenden, weil 7, 12 und 25 paarweise teilerfremd sind.

Beispiele, wie man beim dem erweiterten euklidischen Algorithmus vorgeht findest du mittels der Suchmaschine deiner Wahl oder auf deinem favorisierten Videoportal.

---

Genau das habe ich gemacht und ich komme auf folgendem Ausdruck :

r1 * 7 + s1 * 300 = 1

r2 * 12 + s2 * 175 = 1

r3 * 25 + s3 * 84 = 1

Die Frage stellt sich nun, wie ich r1,r2,r3 und s1,s2,s3 bekomme, sodass 1 auf der rechten Gleichungsseite steht

---

Du braucht r1, r2, r3, s1, s2, s3 nicht bekommen damit 1 auf der rechten Seite steht. In den Gleichungen

r1 * 7 + s1 * 300 = 1

r2 * 12 + s2 * 175 = 1

r3 * 25 + s3 * 84 = 1

steht 1 auf der rechten Seite egal was du für r1, r2, r3, s1, s2 und s3 einsetzt. Außer du hast deinen Computermonitor spiegelverkehrt aufgestellt.

Die Gleichung

r1 * 7 + s1 * 300 = 1

kannst du lösen indem du mit dem euklidischen Algorithmus den ggT von 7 und 300 bestimmst und dann weiter mit dem erweiterten euklidischen Algorithmus machst.

---

Der ggT von 7 und 300 ist 1 also teilerfremd. Deshalb muss auf der rechten Gleichungsseite 1 stehen, aber ich komme beim erweiterten euklidischen Algorithmus nicht weiter.

---

Der ggT von 7 und 300 ist 1

Das ist klar. Schließlich kommt die 300 ja zustande mittels \(12\cdot 25\) und \(7\), \(12\) und \(25\) sind teilerfremd sonst hätte man ja den chinesischen Restsatz nicht anwenden können.

Der euklidische Algorithmus wird nicht deshalb verwendet weil man so wahnsinnig interessiert an dem ggT ist, sondern weil der Rechenweg bis hin zum ggT benötigt wird, um anschließend mit dem erweiterten euklidischen Algorithmus die Gleichung zu lösen.

Deshalb: bestimme mit dem euklidischen Algorithmus den ggT von 7 und 300 obwohl du schon weißt dass er 1 ist.

---

Wenn ich das mache, komme ich auf Folgendes : 300 : 7 = 42Rest6

                                                                            7 : 6 = 1Rest1

Aber ich frage mich noch, wie ich weiter komme. Können Sie mir vielleicht einen hilfreichen Ansatz geben.

---

7 : 6 = 1Rest1

Bedeutung von 1Rest1 ist kontextabhängig. Damit meine ich folgendes:

1. Es ist 13 : 5 = 2Rest3.
2. Es ist 17 : 7 = 2Rest3.
3. Gleichsetzen ergibt 13:5 = 17:7. Das ist jedoch offensichtlich falsch.

Offensichtlich bedeuten 2Rest3 in der ersten und zweiten Zeile unterschiedliches.

Diese Mehrdeutigkeit kann man vermeiden indem man die Form

        a = n·b + c

anstatt

        a : b = nRestc

verwendet. Dann lautet deine Gleichung

        7 = 1·6 + 1.

Diese formt man nach dem Rest um und bekommt

(1)        1 = 7 - 1·6.

300 : 7 = 42Rest6

Wie oben beschrieben formuliert ergibt das

        300 = 42·7 + 6.

Diese formt man nach dem Rest um und bekommt

(2)        6 = 300 - 42·7.

Jetzt setzt man (2) in (1) ein:

      1 = 7 - 1·(300 - 42·7).

Also ist

        1 = 7 - 1·300 + 42·7 = -1·300 + 43·7.

---

Vielen Dank für die Antwort

Bei 175 und 12 wäre das aber nicht der Fall, weil

175 = 12 *14 +7 => 1) 7 = 175 - 12*14

2) 5-2*2 = 1

Da kann ich aber die erste Gleichung nicht in die zweite einsetzen.

Bei der vorigen Gleichung hat das mit Ihrer Berechnung funktioniert. Warum geht das hier nicht ?

---

Euklidischer Agorithmus:

\(\begin{aligned} 175 & =14\cdot12+7\\ 12 & =1\cdot7+5\\ 7 & =1\cdot5+2\\ 5 & =2\cdot2+1 \end{aligned}\)

Letzte Gleichung nach dem Rest umformen

(1)        \(1 = 5 - 2\cdot 2\).

Vorletzte Gleichung nach dem Rest umformen

        \(2 = 7 - 1\cdot 5\)

und in (1) einsetzen

          \(1 = 5 - 2\cdot (7 - 1\cdot 5)\).

            \(1 =5 - 2\cdot 7 + 2\cdot 1\cdot 5\)

(2)        \(1 = 3\cdot 5 - 2\cdot 7\)

Drittletzte Gleichung nach dem Rest umformen

        \(5 = 12 - 1\cdot 7\)

und in (2) einsetzen

         \(1 = 3\cdot (12 - 1\cdot 7) - 2\cdot 7\)

(3)       \(1 = 3\cdot 12 - 5\cdot 7\)

Viertletzte Gleichung nach dem Rest umformen

  \(7 = 175 - 14\cdot 12\)

und in (3) einsetzen

   \(\begin{aligned}1 &= 3\cdot 12 - 5\cdot (175 - 14\cdot 12)\\&=-5\cdot175+73\cdot12\end{aligned}\)

---

Vielen Dank für Ihre Hilfe.

Jetzt habe ich das Ganze verstanden.