Proof of x mod pq = y mod pq

  • Thread starter SpiffyEh
  • Start date
  • #1
194
0

Homework Statement



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.


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?
 

Answers and Replies

  • #2
a|b means a devides b, which means that there exists an integer number n so that b = a*n
 
  • #3
194
0
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!
 
  • #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
 
  • #5
194
0
Is there another way to prove this without LCM?
 
  • #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!
 

Related Threads on Proof of x mod pq = y mod pq

  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
910
Replies
8
Views
6K
Replies
16
Views
4K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
Replies
7
Views
27K
  • Last Post
3
Replies
67
Views
11K
  • Last Post
Replies
1
Views
1K
Top