ab ≡ xb mod (n)
--> Es gibt k aus N mit
ab - xb = kn
b*(a-x) = kn (#)
und b' = b / ggt(b,n) und n ' = n / ggt(b,n)
sind beides nat. Zahlen, da ggt(b,n) sowohl b als auch n teilt.
Und b' und n' sind dann teilerfremd. Aus # wird durch Division durch den ggt
b ' *(a-x) = k * n '
da b ' und n ' teilerfremd, aber b ' Teiler von k * n ' ist, muss
b ' Teiler von k sein.
Damit ist auch k / b ' aus N und es gilt
a - x = (k/b ' ) * n '
Damit hätte man a ≡ x mod (n ' )
und n ' ist ja gerade n / ggt(b,n). q.e.d.
