>>12624173Let gcd(a,b) = z
a = a' z
b = b' z
gcd(a,b) = ac (mod b) translates to
z = a'zc mod b'z or
1 = a'c mod b'
Let c' = c mod b'
From 1 = a'c mod b' and (a',b') = 1 we know c' is uniquely determined (either trough Bézout coefficients or written (a')^(-1) mod b`if you're feeling fancy.
So we have a canonical way of determining the remainder of c modulo b/gcd(a,b) . But what about c itself? c must be of the form c' + k*b'
where 0 < k < z, constrained by gcd(c,b) = 1.
As 0 < c< b, the equation gcd(c,b) = 1 should be trasnlatable into a series or congruence relationships with the factors of b.
Knowing c', we need to find k<z such that gcd (c` + k*b`, b' z) = 1. As gcd (c` + k*b`, b') = gcd (c`, b') = 1 this reduces to
gcd (c` + k*b`, z) = 1.
The existence of an adequate k can probably be proven with the Chinese remained theorem, but I'm too lazy to sketch a full argument.
