Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of x mod pq = y mod pq

  1. Jan 29, 2012 #1
    1. The problem statement, all variables and given/known data

    Show that given x mod p = y mod p and x mod q = y mod q, the following is true:
    x mod pq = y mod pq.
    p and q are distinct primes.

    3. The attempt at a solution
    Here is the proof from someone that I am trying to understand:

    In general, x≡y (mod p) and x≡y (mod q) ⇒ x≡y (mod LCM(p,q)).
    Proof. x≡y (mod p) and x≡y (mod q) implies p|x-y and q|x-y
    implies LCM(p,q)|x-y, which means x≡y (mod LCM(p,q)). (Q.E.D.)
    So, if p and q are different primes, x≡y (mod p) and x≡y (mod q) yield
    x≡y (mod pq).

    I do not understand the proof. Primarily what does p|x-y mean? or any notation with |. Also, how does the LCM(p,q) come in to this?
  2. jcsd
  3. Jan 29, 2012 #2
    a|b means a devides b, which means that there exists an integer number n so that b = a*n
  4. Jan 29, 2012 #3
    Oh ok. That makes more sense. I still don't understand how the LCM comes in but it's starting to come together some more. Thanks!
  5. Jan 29, 2012 #4
    You're welcome. It's weird actually they brought the LCM up, because if p and q are primes, then LCM(p,q)=p*q
    Hope that helps
  6. Jan 30, 2012 #5
    Is there another way to prove this without LCM?
  7. Jan 31, 2012 #6
    don't worry about the LCM. If p and q are primes, then LCM(p,q) = p*q, so it's the same thing!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook