Kongruent und Lösungsmenge?
Hallo wie berechnet man hierzu die Lösungsmenge:
9x = 6 mod 12
7x = 3 mod 12
9x = 5 mod 12 —> hierbei gibt es ja keinen ggt also auch keine Lösung richtig?
3 Antworten
Um die Gleichung der Form
ax = b (mod m) zu lösen kannst du so vorgehen:
Bestimme zuerst ggT(a,m)
Wenn das kein Teiler von b ist, dann gibt es keine Lösung.
Wenn es ein Teiler ist, dann teilst du a, b und m durch den ggT und erhälst damit eine neue Gleichung:
a'x = b' (mod m')
Da hier ggT(a', m') = 1 gilt, ist a' invertierbar bezüglich Modulo m'. Bestimme also das Multiplikative Inverse a'^-1. Und multipliziere die Gleichung damit.
Somit erhälst du, dass alle x die
x = a'^-1 * b' (mod m') erfüllen, die erste Gleichung erfüllen.
Beispiel bei der Ersten Gleichung:
ggT(9, 12)=3 und das teilt 6
Du erhälst somit die Gleichung:
3x=2 (mod 4)
Das Multiplikative inverse von 3 bzgl Mod 4 ist 3 (da 3*3=9=2*4+1)
Also muss x= 6 = 2 (mod 4) gelten
Somit erhälst du die Lösungen:
x = 2 + k*4, wobei k eine beliebige ganze Zahl ist.
Ich löse solche Aufgaben meist "auf die dumme Tour".
Beispiel: 9x = 5 mod 12, bzw. 9x = 6 mod 12
x 9x mod 12
0 0
1 9
2 18 -> 6
3 15 -> 3
4 12 -> 0
und ab hier wiederholt es sich.
Die 6 ist dabei, die 5 nicht.
hierbei gibt es ja keinen ggt also auch keine Lösung richtig?
Deine überlegung ist richtig, du musst es nur sauber ausdrücken
Ansonsten gehst du im zweifel einfach die Multiplikationstabelle dafür durch
Danke, hast du eine Idee wie man bei den anderen herangeht, wenn man einen ggt bestimmt hat?
Was wäre also hier die Lösungsmenge für 9x = 6 mod 12 und heißt das, dass 9x = 5 mod 12 nicht lösbar ist? VG