Zeigen sie: die Gleichung k=m*x mod n hat genau dann Lösung x wenn k teilbar mit ggT(m,n)

Question

Aufgabe:

Zeigen sie: die Gleichung

k = m * x mod n (k,m,n aus Z, 0 <= k < n)

hat genau dann ein Ergebnis x aus Z, wenn die Zahl k durch die Zahl ggT(m,n) teilbar ist.

Problem/Ansatz:

Ich tappe da komplett im Dunkeln und weiß nicht wie ich das beweisen soll.

Comments

Versuch es doch erst einmal mit einem Zahlenbeispiel.

k = m * x mod n (k,m,n aus Z, 0 <= k < n)

m=25; n=15; x=4

25*4 mod 15=10=k

ggT(m,n)=5

k=5*2

:-)