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

• Feb 7th 2013, 01:14 PM
jackGee
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)
• Feb 7th 2013, 01:30 PM
emakarov
Re: Show that if m and n are relatively prime and a and b are any integer,
• Feb 7th 2013, 01:49 PM
jackGee
Re: Show that if m and n are relatively prime and a and b are any integer,
thank you so much. my prof and the textbook didnt cover this topic
• Feb 7th 2013, 07:52 PM
johng
Re: Show that if m and n are relatively prime and a and b are any integer,
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