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

Prove $$x \equiv a \pmod{p}$$ and $$x \equiv a \pmod{q}$$ then $$x \equiv a\pmod{pq}$$ for $$p\neq q$$ 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

A few proofs of the ubiquitous $$\small \bf CCRT = \bf{Constant\!\!-\!\!case \ CRT}\,$$ [Chinese Remainder Theorem].

Theorem (CCRT) \rm\ \ \ \begin{align}&\rm x\equiv a\!\!\pmod{\!p}\\ &\rm x\equiv a\!\!\pmod{\!q}\end{align}\!\iff x\equiv a\pmod{\!pq}\, if $$\rm\,p,q\,$$ are coprime,

$$\rm\qquad said\ equivalently\!:\quad p,q\mid x-a\iff pq\mid x-a,\$$ if $$\ \rm p,q\,$$ are coprime

$$\rm\qquad said\ equivalently\!:\qquad\ \ \ lcm(p,q)\, =\, pq,\ \ if\ \ p,q\,$$ are coprime

Proof $$\$$ For variety we give a few different proofs.

$$\rm(1)\ \ \ x \equiv a\pmod {\!pq}\:$$ is clearly a solution, and the solution is $$\color{#C00}{unique}$$ mod $$\rm\,pq\,$$ by CRT.  [Note: rotely applying the common CRT formula also yields this obvious solution].

$$\rm(2)\ \ \ p,q\:|\:x\!-\!a\iff lcm(p,q)\:|\:x\!-\!a\:$$ by the Universal Property of $$\rm lcm$$.
$$\qquad\!$$ Further $$\rm\:(p,q)=1^{\phantom{|^|}}\!\!\!\!\iff lcm(p,q) = pq,\,$$ by this answer.

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

$$\rm(4)\ \,$$ The list of prime factors of $$\rm\,p\,$$ occurs in one factorization of $$\,\rm x-a\,$$, and the disjoint list of prime factors of $$\rm\,q\,$$ occurs in another. By $$\color{#C00}{uniqueness}$$, the prime factorizations are the same up to order, so the concatenation of these disjoint lists of primes occurs in $$\rm\,x-a,\,$$ hence $$\rm\,pq\mid x-a$$.

$$\rm(5)\ \,$$ Applying the mod Distributive Law, a handy operational form of CRT

$$\rm p\mid x\!-\!a\,\Rightarrow\, x\!-\!a\bmod pq = p\left[\dfrac{\color{#c00}{x\!-\!a}}p\bmod q\right] = p[\color{#c00}0]=0\ \ {\rm by}\ \ \color{#c00}{x\equiv a}\!\!\!\pmod{\!q}\qquad$$

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.

More generally this idea works for values & moduli in A.P. $$\$$ if $$\,(a,b) = 1\,$$ then

APCRT $$\ \ \left\{\,x\equiv d\!-\!ck\!\pmod{b\!-\!ak}\,\right\}_{k=0}^{n}\!\!\iff\! x\equiv \dfrac{ad\!-\!bc}a\!\!\!\pmod{{\rm lcm}\{b\!-\!ak\}_{k=0}^n}$$
 e.g. here $$\ \underbrace{\left\{\,x \equiv 3-k\pmod{7-k}\,\right\}_{k=0}^2}_{\!\!\!\!\!\!\textstyle{x\equiv 3,2,1\pmod{\!7,6,5}}}\!\iff x\equiv \dfrac{1(3)\!-\!7(1)^{\phantom{|^{|^|}}}}1\equiv -4\pmod{\!210}$$

• 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]=\operatorname{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$.