Question

Is there a way to use the Chinese Remainder Theorem if GCF isn't 1 for the moduli (example in a comment)?

Answer 1

From a textbook:
Solve the system ([11][18])
X congruent to 17 (mod 504)
X congruent to -4 (mod 35)
X congruent to 33 (mod 16)

Answer 2

X congruent to 17 (mod 16)

Answer 3

LCM(504,16)=1008, 1008 congruent to -7 (mod 35).
X congruent to 31 (mod 35)
X+1008 congruent to 24 (mod 35)
X+2016 congruent to 17 (mod 35)

Answer 4

Therefore, X+2016 congruent to 17 (mod 504, mod 35, mod 16)

Answer 5

Therefore, X+1999 congruent to 0 (mod 504, mod 35, mod 16)

Answer 6

Therefore, X = LCM(504,35,16)n + 1999 = 5040n+1999

Answer 7

By the way the Chinese Remainder Theorem requires the moduli to be pairwise coprime.

Answer 8

Thanks, that was what I was wondering. I was thinking there might be a way to wrestle it into a form that could be used with the CRT. Thanks for your help :)