Specializing general CRT formula when residues are constant

205 Views Asked by At

Both $p, q$ are prime

$x \equiv y \pmod p$
$x \equiv y \pmod q$

Using Chinese remainder theorem,

$M = p*q$
$x = a1*b1*M/p + a2*b2*M/q$

$x = a1*b1*q + a2*b2*p$

$a1 = y$
$a2 = y$

$b1$ is solution of $(M/p)*x \equiv 1 \pmod p$

i.e. soln of $qx \equiv 1 \pmod p$

Likewise $b2$ is solution of $px \equiv 1 \pmod q$

$q$ & $q$ are prime - so they are co-prime to each other.

So $b1 \equiv (1/q) \pmod p$ ----> (1)

$b2 \equiv (1/p) \pmod q$ ----> (2)

So $x \equiv y*b1*q + a2*b2*q$ ---> (3)

From (1), (2) & (3) is it possible to arrive at

$x \equiv y \pmod{p*q}$

I know it's possible to prove the above in a much more easy way, but I was wondering if it's possible to prove this using CRT?

1

There are 1 best solutions below

0
On

Yes, rotely applying the common CRT formula yields the unique solution

$$ x\,\equiv\, y\,\overbrace{(p(p^{-1}\bmod q) + q(q^{-1}\bmod p))}^{\textstyle u} \pmod{pq}$$

Note $\,u\equiv 1\,$ both mod $\,p$ & $q.\,$ This has obvious solution $\,\color{#c00}{u\equiv 1}\pmod{pq}$ which is unique $\!\bmod pq\,$ by CRT. $ $ Thus $\,x\equiv y\color{#c00}u\equiv y\cdot \color{#c00}1\equiv y\pmod{\!pq},\,$ as claimed.

So rotely applying the CRT formula does indeed solve this constant case of CRT, but it's wasteful. The formula yields the existence of a solution, but that is trivial here since there is an obvious solution $\,x\equiv y\pmod{\!pq}.\,$ So here we need only uniqueness, i.e. proof that this obvious solution is the only solution $\!\bmod pq,\,$ for which see the various proofs of CCRT = Constant-case CRT.