# Thread: Chinese Remainder Theorem Help

1. ## 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!

2. ## 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.

3. ## 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?

4. ## 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.