4.3 Chinese Remainder Theorem

Chinese Remainder Theorem

Given pair-wise coprime moduli $n_1,\dots ,n_k$ and their product $N={\prod }_{i=1}^k{n}_i$, the Chinese Remainder Theorem states that there exists a unique integer $0\le x\le N-1$ that simultaneously satisfies $x\equiv a_i(\mathrm{mod}{n}_i)$ for all $i=1,2,\dots ,n$.

Moreover, writing $N_i=N/n_i$ and letting $N_i^{-1}$ denote the modular inverse of $N_i(\mathrm{mod}{n}_i)$, the unique solution for $x$ can be explicitly constructed as
$x\equiv {\sum }_{i=1}^k{a}_i\left(N_i{N}_i^{-1}\right)(\mathrm{mod}N),$
where $N_i{N}_i^{-1}$ are the basis residues, such that $N_i{N}_i^{-1}\equiv 1(\mathrm{mod}{n}_i)$ and $N_i{N}_i^{-1}\equiv 0(\mathrm{mod}{n}_j)$ for all $n_j\ne n_i$.

Intuition

Although difficult in theory, the CRT is based on the following claim:

• For $m,n$ with $\gcd (m,n)=1$ that there is exactly one $x(\mathrm{mod}mn)$ that satisfies the equations $x\equiv a(\mathrm{mod}n)$ and $x\equiv b(\mathrm{mod}m)$.

The proof for this claim is as follows. Let $u\equiv m(m^{-1}(\mathrm{mod}n))$ and $v\equiv n(n^{-1}(\mathrm{mod}m))$. Then, $u\equiv 1(\mathrm{mod}n)$ and $u\equiv 0(\mathrm{mod}m)$, whereas $v\equiv 0(\mathrm{mod}n)$ and $v\equiv 1(\mathrm{mod}m)$. This means that $x=ua+vb\equiv (1)a+(0)b\equiv a(\mathrm{mod}n)$, and similarly $x\equiv b(\mathrm{mod}m)$, meaning we have an $x$ satisfying the equation.

Examples

How Many Solutions?

Consider the equation $ax\equiv b(\mathrm{mod}pq)$ for distinct primes $p,q$. In the below three parts, all values $a,b,x$ are defined as values in in the range $\{0,1,\dots ,pq-1\}$.

If $\gcd (a,pq)=p$, show that there exists a solution if and only if $b=0(\mathrm{mod}p)$. We proceed in the following way:

• Sufficiency ($⟹$): Since $b=0(\mathrm{mod}p)$, this means that $b$ is also a multiple of $p$. As such, we can express $\frac{a}{p}x=\frac{b}{p}+kq$, which reduces to $\frac{a}{p}x\equiv \frac{b}{p}+mpq\equiv \frac{b}{p}(\mathrm{mod}q)$. This congruence has a solution as long as $\gcd (a/p,q)=1$ (i.e., $a/p$ is invertible). We know that this requirement is satisfied since $\gcd (a,pq)=p$, meaning that $p\mid a$, but $q\nmid a$.
• Necessity ($⟸$): Let $ax=b+kpq$. Since $\gcd (a,pq)=p$, then $0\equiv b+0(\mathrm{mod}p)$.

If $\gcd (a,pq)=p$, and there is a solution $x$, show that there are exactly $p$ solutions. a

For how many pairs $(a,b)$ are there exactly $p$ solutions?

Since $\gcd (a,pq)=p$, $a\equiv b\equiv 0$ as shown in the last step. We know that all solutions are of the form $\frac{a}{p}x=\frac{b}{p}+kq$. Therefore, it must be that $q\mid \left(\frac{a}{p}x-\frac{b}{p}\right)$. Since $\gcd (a,q)=1$, then $a/p$ is invertible, and we get $x\equiv (a/p{)}^{-1}b$. We lift to modulo $pq$, where we get In the set $\{0,1,\dots ,pq-1\}$ there are exactly $p$ multiples of $q$ (including $0$) that satisfy this condition given the right values of $a,b$.

Celebrate and Remember Textiles

You’ve decided to knit a 70-themed baby blanket as a gift for your cousin and want to incorporate rows from three different stitch patterns with the following requirements on the row lengths of each of the stitch patterns:

• Alternating Link: Multiple of 8, plus 3
• Double Helix: Multiple of 3, plus 1
• Crossover: Multiple of 7, plus 6

You want to be able to switch between knitting these different patterns without changing the number of stitches on the needle, so you must use a number of stitches that simultaneously meets the requirements of all three patterns.

Find the smallest number of stitches you need to cast on in order to incorporate all three patterns in your baby blanket.

We must solve using CRT for the following system of equations:

x \equiv 3 \pmod{8}, \
x \equiv 1 \pmod{3}, \
x \equiv 6 \pmod{7}.
\end{cases}$$

We construct $N=168$, and therefore $N_1=21$, $N_2=56$, $N_3=24$. A quick application of EGCD finds that the inverses are $N_1^{-1}=5$, $N_2^{-1}=2$, and $N_3^{-1}=5$. Therefore, $x\equiv 3\cdot (21\cdot 5)+1\cdot (56\cdot 2)+6\cdot (24\cdot 5)(\mathrm{mod}168),$which simplifies to $x\equiv 139(\mathrm{mod}168)$.