Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$p$ and $q$ are distinct primes.

Where can I start with this proof? It looks similar to the Chinese Remainder Theorem, but that deals with two different a values.

share|improve this question
    
but that deals with two different $a$ values - What makes you think that? –  anon Sep 3 '12 at 15:59
    
Because for the explanations of Chinese Remainder Theorem I've read, they use something like a = x (mod p) and a = y (mod p) –  Takkun Sep 3 '12 at 16:03
2  
A couple of variables denoted with two different letters may take on two different values, but not necessarily unless they are explicitly stated to have distinct values. –  anon Sep 3 '12 at 16:04

3 Answers 3

up vote 5 down vote accepted

Hint $\ $ Below are few possible proofs of this constant-case of Chinese Remainder Theorem (CRT).

$\rm(1)\ \ \ x \equiv a\pmod {pq}\:$ is clearly a solution, and the solution is $\color{#C00}{unique}$ mod $\rm\,pq\,$ by CRT.

$\rm(2)\ \ \ p,q\:|\:x\!-\!a\iff lcm(p,q)\:|\:x\!-\!a.\:$ Further $\rm\:(p,q)=1\iff\:lcm(p,q) = pq.$

$(3)\ \, $ By Euclid's Lemma: $\rm\:(p,q)=1,\ p\:|\:qn =\:x\!-\!a\:\Rightarrow\:p\:|\:n\:\Rightarrow\:pq\:|\:nq = x\!-\!a.$

$\rm(4)\ \, $ Since the prime factorization of $\rm\,x\!-\!a\,$ is $\color{#C00}{unique}$, and the prime $\rm\,p\,$ occurs in one factorization, and the distinct prime $\rm\,q\,$ occurs in another, both factorizations are the same up to order, hence contain both $\rm\,p\,$ and $\rm\,q,\:$ hence have $\rm\,pq\,$ as a divisor.

Remark $\ $ This constant-case optimization of CRT arises frequently in practice so is well-worth memorizing, e.g. see some prior posts for many examples.

Quite frequently, $\color{#C00}{uniqueness}\ theorems$ provide powerful tools for proving equalities.

share|improve this answer
    
in (2) do you mean to say $gcd(p, q) = 1 \iff lcm(p, q) = pq$ –  CodeKingPlusPlus Sep 23 '12 at 23:17
    
@Code Yes, $\rm\:(x,y)\:$ means $\rm\:gcd(x,y)\:$ in number theory (common notation). –  Bill Dubuque Sep 23 '12 at 23:37

Let $[A,B]=lcm(A,B)$ and $(A,B)=gcd(A,B)$

If $p,q$ are different integers, $p\mid(x-a)$ and $q\mid(x-a)\implies [p,q]\mid(x-a)$

We know $[p,q]\cdot (p,q)=p\cdot q$

If $(p,q)=1, [p,q]=p\cdot q$

If $p,q$ are distinct primes, $(p,q)=1$

share|improve this answer

Let $y=x-a$. We want to show that if $p$ divides $y$ and $q$ divides $y$ then $pq$ divides $y$.

Since $p$ divides $y$, we have $y=pz$ for some $z$. Thus $q$ divides $pz$. Since $q$ is prime, this implies $q$ divides $p$ or $q$ divides $z$. But $q$ cannot divide $p$, so $q$ divides $z$. Suppose that $z=qw$. Then $y=pqw$.

share|improve this answer

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.