Kongurenzgleichung / Multiplikative inverse

Question

Aufgabe:

Lösen Sie 7 + 6x = 1 in Z16

Problem/Ansatz:

7+ 6x Ξ 1 mod 16  | -7

6x Ξ -6 mod 16

jetzt muss ich doch die multiplakative inverse von 6 in Z16 finden aber wie?

Answer 1

Jetzt muss ich doch die multiplakative Inverse von 6 in Z16 finden,...

Ja, aber das geht hier auch einfacher.

...aber wie?

Da es nur wenige Kandidaten gibt, wäre "Ausprobieren" eine mögliche Strategie.

Answer 2

jetzt muss ich doch die multiplakative inverse von 6 in Z16 finden aber wie?

Das wird leider nicht möglich sein, da 6 nicht invertierbar ist;

dennoch ist x=15 eine Lösung der Kongruenz, aber auch x=7,

wie man leicht nachprüft.

Answer 3

7 + 6x = 1 MOD 16

6x = -6 MOD 16

3x = -3 MOD 8

x = -1, 7, 15 MOD 8

Probe

7 + 6*7 = 1 MOD 16

49 = 1 MOD 16

3*16 + 1 = 1 MOD 16

1 = 1

Comments

So kann man das nicht machen, da 6 nicht teilerfremd zu

16 ist.

---

Ja aber wo mache ich genau den Fehler und warum bekomme ich dann das richtige Ergebnis heraus?

---

Der ggT von 6 und 16 ist $d=2$. Daher gilt

$6x\equiv -6$ mod $16\iff 6/d\cdot x\equiv -6/d$ mod $16/d$,

also $3x\equiv -3$ mod $8$, ...

---

Wenn 6x = -6 ist, warum gilt dann nicht x = -1 wie ich geschrieben habe. Ich wollte wissen wo ich genau den Fehler gemacht habe und nicht wie du es notieren würdest.

---

Weil in Wirklichkeit nicht

$6x\equiv -6$ mod $16 \Rightarrow x\equiv -1$ mod $16$, sondern

$6x\equiv -6$ mod $16 \Rightarrow x\equiv -1$ mod $16$$\; \vee \; x\equiv 7$ mod $16$

gilt.

---

Ah. Also entgeht mir dann nur Lösungen. Ok. Ich korrigiere das oben.

---

Ja. Deine Lösung ist ja nicht falsch, aber die Lösungsmenge ist
nicht komplett ;-)

---

Ja. Deine Lösung ist ja nicht falsch, aber die Lösungsmenge ist
nicht komplett ;-)

Prima. Vielen Dank für den Hinweis.