0 Daumen
2,1k Aufrufe

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 ?

Avatar von

1 Antwort

0 Daumen

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

Avatar von 487 k 🚀

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community