# Chinese Remainder Theorem Help

• Sep 17th 2012, 08:49 AM
BBSCZenom
Chinese Remainder Theorem Help
This homework is due soon and i can't get this one problem... it's driving me crazy.

Here it is: Prove and extend or disprove and salvage (with another if and only if statement):
Statement: Let m and n be two relatively prime integers each greater than 1. Then for integers a and b, the system of simultaneous linear congruences
ax=b mod m
ax=b mod n
(the "=" is supposed to be three lines instead of two, meaning "congruent to")
has a solution of integer x if and only if there is an integer solution to the linear congruence
ax=b mod mn
(again, three lines on the "=")

You don't have to write out a formal proof for me, just help me understand this and lead me in the right direction so i can write a proof for it. Thanks!
• Sep 17th 2012, 04:47 PM
johnsomeone
Re: Chinese Remainder Theorem Help
To just understand what's going on, maybe look at it this way:
Let w = ax-b, and then reformulate that statement in terms of n, m, and w.
Forget about the "has a solution" part, and just see what it's saying about n, m and w.
• Sep 21st 2012, 06:37 AM
BBSCZenom
Re: Chinese Remainder Theorem Help
is it an accurate proof to assume the if and only if statement and then derive the system of linear congruences from the if and only if statement?
• Sep 21st 2012, 02:08 PM
johnsomeone
Re: Chinese Remainder Theorem Help
I don't understand that, but I'm pretty sure the answer is no. If you're going to prove something, you need to prove it.
Think about the lemma below. Can you prove it? How does it relate to the problem?

Lemma: Suppose n, m and w and integers, and that the gcd(n, m) = 1. Then "w = 0 mod n" and "w = 0 mod m" are both true
if and only if "w = 0 mod (mn)" is true.