Erweiterter Euklidischer Algorithmus ggT

Question

Aufgabe

(Erweiterter Euklidischer Algorithmus II)

Zeigen Sie: Die Gleichung
k = m · x mod n (k, m, n ∈ Z, 0 ≤ k < n)
hat genau dann eine Lösung x ∈ Z, wenn die Zahl k durch die Zahl ggT(m, n) teilbar ist.

Problem/Ansatz:

Kann mir jemand helfen, ich bin ratlos. Bis dahin habe ich es geschafft, doch jetzt weiß ich nicht weiter...

Comments

Zeige zwei Implikationen:

k = m x mod n hat Lösung x <=> ggT(m,n) teilt k

=>: Sei x eine Lösung von k = mx mod n dann ist k-mx = 0 mod n, d.h. n ist ein Teiler von k-mx und daraus folgt es existiert ein y mit k-mx = n*y, umformen liefert k = m*x + n*y.

Warum folgt daraus, dass ggT(m,n) ein Teiler von k ist?

<=: Stelle den ggT als Linearkombination dar: d := ggT(m,n) = a*m + b*n

da d | k existiert ein k' mit k = d * k'. Multiplizieren wir obige Gleichung mit k' erhalten wir

k = d * k' = m*(a*k') + n * (b*k')

Was ist hier jetzt eine mögliche Lösung x?

---

Danke.

Kann ich bei der 2. Implikation ( k = d * k' = m*(a*k') + n * (b*k') ) für k dann mx mod n einsetzen und bekomme dann eine Lösung für x oder wie muss ich vorgehen?

---

Was erhältst du denn wenn du

k = m*(a*k') + n * (b*k')

modulo n betrachtest? Bzw. was passiert mit dem zweiten Summand?

---

Erhalte ich das: k = ma * mk' + nb * nk' ?

Ist dann ma * mk' + nb * nk' = mx mod n ?

Und welchen Schluss kann ich dann daraus ziehen?

---

Nicht ganz, da stehen außerdem überall * und keine +, warum wendest du hier eine Art Distributivgesetz an?. Modulo n lässt alle Terme der Form n*(Irgendwas) verschwinden

Die Gleichung k = m*(a*k') + n * (b*k')

wird modulo n also zu

k = m * (a* k') mod n

Wenn du das jetzt mit der Gleichung

k = m * x mod n

Vergleich beide mal, dann sollte dir ein geeigneter Kandidat für x einfallen.

---

Ist dann x=a*k' ?

Und das teilt dann den ggT von (m,n), weil d (ggT) mit k' multipliziert wird?

---

Ist dann x=a*k' ?

Ja, das ist eine Möglichkeit.

Und das teilt dann den ggT von (m,n), weil d (ggT) mit k' multipliziert wird?

Was teilt den ggT?

In der zweiten Implikation geht es nur darum eine Lösung für k = mx mod n zu finden WENN ggT(m,n) ein Teiler von k ist.

in diesem Schritt musst du also keine Teilbarkeit zeigen, da diese ja als Prämisse vorausgesetzt wurde.

Nur in der anderen Implikation: WENN k = mx mod n eine Lösung hat DANN ist ggT(m,n) | k.

---

jetzt hab ichs, danke :)