9x kongruent 12 modulo 15 Lineare Kongruenz lösen Frage

Question

Hallo ich habe folgende Aufgabe:

Die Aufgabe 9x kongruent 12 (mod 15) ist zu lösen.

Ich habe den Ansatz, dass ggT(9,15) = 3

Dann habe ich mit dem erweiterten euklidischen Algorithmus:

3 = 2*9 - 15    / *4

12 = 8*9 - 4*15

umgeformt zu: 12 = 8*9  - 15*9

Demnach ist 8 eine Lösung und somit x = 8 + k*15 mit k aus Z.

Jedoch wäre 3 auch eine Lösung, welche ich jedoch nicht mit meiner Lösungsmenge finden kann.

Kann mir jemand den Fehler sagen ?

Answer 1

Wenn 15, 12 und 9 alles durch 3 teilbar ist. Darf man dann nicht gleich alles durch 3 teilen?

Es gilt doch

9x + 15y = 12

also auch

3x + 5y = 4

Eigentlich hätte ich dann probiert diese Gleichung zu lösen.

3*2 + 5*(-1) = 1

3*8 + 5*(-4) = 4

Also ist die Lösung 

x = 8 + k*5

Comments

Ja, aber warum komme ich denn mit meiner Lösung nicht auf alle Lösungen ?

Wenn ich für k Werte Einsetze stimmt die Konrguenz immer aber z.B. die 3 ist nicht in der Menge obwohl für x =3 es auch passt...

---

weil du ja immer nur werte von 15 dazu addiert. dadurch gehen dir die Lösungen wie 3 und 13 verloren.

Wie gesagt hat man ja eine Lösung bei

x = 8 + k*5

---

Gibt es dann einen Weg wie ich Kongruenzen lösen ohne das mir Werte verloren gehen ?

---

Ist meines kein Weg?

---

Doch schon, aber wenn ich aber Kongruenzen mit größeren Zahlen wird es mit dem Probieren

schwierig. Deshalb frage ich mich warum ich keine Äquivalenzumformungen habe bzw. wo der Fehler liegt.

---

Eigentlich sollten bei dir doch gleich Alarmglocken angehen wenn du als ggT den Wert 3 bekommst.

Damit lassen sich über eine Linearkombination ja nur vielfache von 3 darstellen. Damit 12 eine Lösung sein kann muss 12 also auch durch 3 teilbar sein. Ist es ja auch. Und deswegen kann man die Gleichung gleich vereinfachen. Notfalls vorher prüfen ob 12 durch 3 teilbar ist.

---

Okay, wie würde das bei dem Beispiel 45x  kongruent 8 ( mod52) aussehen ?

Mit meinem Ansatz hätte ich -120 + 52k als Lösung ?

Ist das korrekt ?

---

Ja. Allerdings darfst du zu -120 gerne 2 oder 3 mal 52 hinzuaddieren. Ich hätte also geschrieben

x = 36 + 52*k

---

Aber komischerweise habe ich das genauso gemacht wie oben also

1) ggT --> Linearkombination erstellt und dann mit einem Wert multipliziert aber diesmal habe ich

alle Werte gefunden ?

---

Was ist den der GGT von 45, 8 und 52 ? Das ist doch 1 oder nicht ?

---

Nein, ich meine bei der ersten Aufgabe - warum ich nicht auf die 3 oder 13 komme wo da der Fehler liegt ?

---

Weil du halt davon ausgehst, dass deine Lösungen Modulo 15 auseinander liegen. Und gerade das ist ja verkehrt.

Wenn ich jetzt sage

5x ≡ 1 mod 4

Dann sehen wir das 1 + 4k eine Lösung ist

Wenn ich jetzt schreibe

500x ≡ 100 mod 400

Was sind dort jetzt die Lösungen ? 

---

1 + 400k ? Oder?

---

Dann ist 5 keine Lösung?

---

Doch eben schon aber das ist wieder das Problem:

Das ich mit 1 + 400k nicht auf 5 komme.

---

Durch 100 ist es ja eh immer teilbar. Darum brauchst du eben das nicht mit in der Gleichung haben.

Also wenn du die Gleichung

500x ≡ 100 mod 400 

hast, dann teilst du erstmal sowieso alles durch 100. weil das ja eh immer erfüllt ist.

Lösen brauchst du also nur 

5x ≡ 1 mod 4

Und dann bekommst du eben auch alle Lösungen hin.

---

Also kann ich immer erstmal durch den ggT teilen richtig ?

---

Genau. Und dann ließ dir noch mal die erste Zeile meiner ersten Antwort durch.

---

Aber das Modul muss ich auch durch den ggT Teilen richtig ?

Ich habe noch eine Zweite Frage zu Modul. Rechnen

2^1371 mod 71 soll berechnet werden.

---

Über eine Wertetabelle findet man schnell

2^35 ≡ 1 mod 71

Und damit ist die Aufgabe dann auch recht schnell zu lösen.

Wie man allerdings schneller als über eine Wertetabelle herankommst, dass weiß ich nicht.

---

Gibt ja noch die Sätze von Willson,...

Aber Danke erstmal !

---

Aber wenn ggT = 1 ist dann sollte das schon funktionieren oder?

---

Ja. Dann sollte des Funktionieren.