(adsbygoogle = window.adsbygoogle || []).push({}); 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Proof of x mod pq = y mod pq

**Physics Forums | Science Articles, Homework Help, Discussion**