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.