This is the Chinese remainder theorem.
This is the Chinese remainder theorem.
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