Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am supposed to prove that x = y mod (p*q) <=> x = y mod p and x = y mod q with p and q are prime numbers. It somewhat sounds reasonable to me, but unfortunately I don't have any clue how to prove it.

share|improve this question
4  
Recall the definition for when two numbers are congruent modulo some number. Then prove for yourself that if two numbers are congruent modulo some product, they are also congruent modulo the factors of the product. Then prove for yourself that if two numbers are congruent modulo two different moduli, then they are congruent modulo the least common multiple of the moduli. Then apply these results, and you are done. –  K.G. Jun 5 at 11:15
    
@K.G. You really should’ve posted that as an answer… it surely would be an acceptable one (that is, from my point of view). –  e-sushi Jun 5 at 13:05

1 Answer 1

up vote 2 down vote accepted

That the left hand side implies the right hand side is easy, it follows from the following fact:

$$x\equiv y \mod{pq}\ \Leftrightarrow pq \mbox{ divides }x-y \Rightarrow p \mbox{ divides } x-y \mbox{ and } q \mbox{ divides }x-y$$

And so $x\equiv y \mod{p}$ and $x\equiv y \mod{q}$

Now, the point here is argument can be "reversed" in the case that $p$ and $q$ are relatively primes (and actually they are since we are assuming that they are different, if they're not, we can't obtain the result), it is, if $x\equiv y \mod{p}$ and $x\equiv y \mod{q}$, then p $\mbox{ divides } x-y$ and $q \mbox{ divides }x-y$, and as $p$ and $q$ are relatively prime (this is a well known theorem in number theory) we have that $pq$ divides $x-y$, thus $x\equiv y \mod{pq}$.

This is the general version of theorem I've wrote before:

Let $a,b,n\in \mathbb{Z}$ and suppose that $a$ divides $n$ and $b$ divides $n$, then $ab$ divides $n\cdot \mbox{gcd}(a,b)$. This, in the case that $a,b$ are relatively prime, gives the result i'm reffering to (because in that case $\mbox{gcd}(a,b)=1$).

Here's a small proof of this fact. Let $n=as$ and $n=bt$, write $\mbox{gcd}(a,b)=g$, we know that there exists $x,y$ integers such that $ax+by=g$ (see this post), then, multiplying this expression by $n$, we obtain $n(ax)+n(by)=ng$, replacing adequately, we have $(bt)(ax)+(as)(by)=ng$ and rearranging, we finally obtain $(ab)(xt+ys)=ng$ so $ab$ divides $ng=n\cdot \mbox{gcd}(a,b)$.

share|improve this answer
    
Could you post the theorem you are reffering to? Or a link to it. –  CGFoX Jun 6 at 9:53
    
It's done, I've edited my answer. –  Devilathor Jun 6 at 11:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.