# Prove $x \equiv a \pmod{p}$ and $x \equiv a \pmod{q}$ then $x \equiv a\pmod{pq}$

$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.

-
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
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

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.

-
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$

-

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$.

-