Für welche natürlichen Zahlen m ist die Gleichung 126 x \equiv 105(\bmod (m)) lösbar?

Question

Aufgabe:

Für welche natürlichen Zahlen \( m \) ist die Gleichung \( 126 x \equiv 105(\bmod (m)) \) lösbar?
Anmerkung: Hier ist eine möglichst explizite Beschreibung der unendlichen Menge an möglichen Werten für \( m \) gesucht. Verwenden Sie dafür die Primfaktorzerlegung.

Problem/Ansatz:

Wie genau kann man das mit der PFZ machen? Ich hätte gesagt alle Lösungen sind, wenn man jeweils zu der Lösung für x, immer für ax, m dazuaddiert bzw. -m

Answer 1

\(6x\equiv 5\) mod \(m\) ist genau dann lösbar, wenn \(ggT(m,6)=1\) ist, d.h.

\(m\) weder \(2\), noch \(3\) als Primteiler besitzt; in diesem Falle gilt:

\(6x\equiv 5\Rightarrow 126x=21\cdot 6x\equiv 21\cdot 5=105\) mod \(m\).

Hinzu kommen noch die Möglichkeiten m=3, 5, 7, 15, 21, 35, 105

also alle Teiler von 105. Das sind also zusätzlich m=3,15,21,105.

Comments

Wie genau kommst du auf 21*6x und 21*5 ?

---

Ich habe mir die Primfaktorzerlegung von

126 und 105 angeschaut: ggT(126,105)=21.

---

Okay danke jetzt hab ich's verstanden, hab das alles nochmal so nachgerechnet und bei mir war alles gleich bis auf m=7, 7 sollte doch auch enthalten sein oder?

m=7

126=2*3*3*7

105=3*5*7

Oder übersehe ich da irgendwas?

---

Für m=7 gilt doch ggT(m,6)=1, also ist der Fall abgedeckt.