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.

  • 1
    $\begingroup$ but that deals with two different $a$ values - What makes you think that? $\endgroup$
    – anon
    Sep 3 '12 at 15:59
  • $\begingroup$ Because for the explanations of Chinese Remainder Theorem I've read, they use something like a = x (mod p) and a = y (mod p) $\endgroup$
    – Takkun
    Sep 3 '12 at 16:03
  • 5
    $\begingroup$ 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. $\endgroup$
    – 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}$

  • $\begingroup$ in (2) do you mean to say $gcd(p, q) = 1 \iff lcm(p, q) = pq$ $\endgroup$ Sep 23 '12 at 23:17
  • $\begingroup$ @Code Yes, $\rm\:(x,y)\:$ means $\rm\:gcd(x,y)\:$ in number theory (common notation). $\endgroup$ 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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