Thread: Show that if m and n are relatively prime and a and b are any integer,

Show that if m and n are relatively prime and a and b are any integer,
then there is an integer x that simultaneously satisfies
the two congruence x ≡ a (mod m) and x ≡ b (mod m)

This is the Chinese remainder theorem.

thank you so much. my prof and the textbook didnt cover this topic

Here's a very simple constructive proof:
Form the sequence a+mi, 0<=i<n. If two of these were the same mod n, a+mi=a+mj mod n, m(i-j)=0 mod n. Since n and m are relatively prime, n divides i-j and i=j. So the sequence forms a complete set of remainders mod n; b mod n must be one of these. Actually, there's more: the x is unique mod mn, but I won't bother with a proof.

Since the above proof is constructive, for "small" m and n, you can rapidly find the x. Example: suppose you know the last two digits of a positive integer are 7 mod 25 and 1 mod 4. Then the sequence is 7+25=32, 7+2*25=57 which is 1 mod 4. So the last two digits are 57