Understanding the Proof of x mod pq = y mod pq for Distinct Primes p and q

  • Thread starter SpiffyEh
  • Start date
  • Tags
    Proof
In summary, the conversation discusses a proof involving the concepts of mod and LCM (least common multiple). The proof shows that if x is congruent to y mod p and x is congruent to y mod q, then x is also congruent to y mod the LCM of p and q. This holds true for distinct prime numbers p and q. The notation p|x-y means that p divides x-y. It is also mentioned that LCM(p,q) is equal to p*q if p and q are primes.
  • #1
SpiffyEh
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 into this?
 
Physics news on Phys.org
  • #2
a|b means a devides b, which means that there exists an integer number n so that b = a*n
 
  • #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!
 
  • #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
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!
 

FAQ: Understanding the Proof of x mod pq = y mod pq for Distinct Primes p and q

1. What is the purpose of a proof of x mod pq = y mod pq?

A proof of x mod pq = y mod pq is used to show that two numbers, x and y, have the same remainder when divided by the product of two other numbers, p and q. This is often used in number theory and cryptography to verify the validity of calculations and algorithms.

2. How is a proof of x mod pq = y mod pq different from a regular proof?

A proof of x mod pq = y mod pq is a specific type of proof that deals with modular arithmetic. Unlike a regular proof, it involves taking the remainder of a number when divided by another number, rather than just looking at the numbers themselves. It also requires a different set of mathematical tools and techniques.

3. Can a proof of x mod pq = y mod pq be used to solve equations?

Yes, a proof of x mod pq = y mod pq can be used to solve equations involving modular arithmetic. By showing that two numbers have the same remainder when divided by pq, you can infer that they are equivalent in terms of modular arithmetic and use this information to solve the equation.

4. What are some real-world applications of a proof of x mod pq = y mod pq?

Proofs of x mod pq = y mod pq have many practical applications, particularly in the field of cryptography. They are used to verify the correctness and security of encryption and decryption algorithms, as well as in digital signature schemes and other cryptographic protocols.

5. Are there any limitations to a proof of x mod pq = y mod pq?

One limitation of a proof of x mod pq = y mod pq is that it only applies to numbers that are relatively prime to pq. This means that the numbers being compared cannot have any common factors with pq, otherwise the proof will not hold. Additionally, this type of proof can only be used to compare the remainders of two numbers, and does not provide information about the actual values of the numbers themselves.

Similar threads

If ## p\geq q\geq 5 ## and ## p ## and ## q ## are both primes ....
Replies
30
Views
2K
If a and b are both quadratic residues/nonresidues mod p & q
Replies
1
Views
2K
U(n) as an External Direct Product
Replies
11
Views
1K
Can Discrete Logarithms Be Added in Modular Arithmetic?
Replies
16
Views
1K
Congruence and Primes: Proving the Order of an Integer Modulo a Prime
Replies
4
Views
1K
Prove that if p > 3 is a prime number, then p^2 = [....]
Replies
16
Views
2K
Direct Proof that every zero of p(T) is an eigenvalue of T
Replies
24
Views
2K
I Proof for subgroup -- How prove it is a subgroup of Z^m?
Replies
11
Views
2K
Solving x^2=1 (mod pq) with Odd Primes
Replies
2
Views
2K
Abstract Alg. Proof w/ Mod Congruence and Relative Primes
Replies
1
Views
912

Hot Threads

Recent Insights

Back
Top