Let f g h s and t be integers with k 1 If gcd f k h and g

Let f, g, h, s and t be integers with k > 1. If gcd (f, k) = h and g = f (mod k), then gcd (g, k) = h. Let f, g, h, s and t be integers with f > g > h > 1. If s = t (mod f), s = t (mod g) and gcd (f, g) = h, then sh = th (mod f g).

Solution

gcd (f, k) = h

a*h = f, & b*h = k, for some integers a and b

g = f (mod k)

g = k*n + f

g = b*h*n + a*h

g = h*(b*n + a)

which proves that

g = h*c, where c = (bn + a) is an integer

Also we know that

k = h*b

this proves that

gcd (g, k) = h