1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof of x mod pq = y mod pq
  1. P+q = pq Hölder (Replies: 3)

  2. Integer mod proof (Replies: 5)

Loading...