LinkBack URL
About LinkBacksTo 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.
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!
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.
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.
  |
