[Math] Find all solutions using the Chinese Remainder Theorem

chinese remainder theoremcongruenceselementary-number-theorymodular arithmetic

Find all solutions using the Chinese Remainder Theorem.

$$
\begin{cases}x \equiv 3 \pmod{4}\\
x \equiv 5 \pmod{21}\\
x \equiv 7 \pmod{25}
\end{cases}$$

I can see that $4$,$21$, and $25$ are all pairwise relatively prime. I then proceeded to use$ Z=(C_1)\times(X_1)\times(B_1) +(C_2)\times(X_2)\times(B_2) +(C_3)\times(X_3)\times(B_3)$.
Let $C_i $ be the remainder and$ b_i$ be the modulus.
$3=C_1,5=C_2,7=C_3$.
$4=b_1,21=b_2,25=b_3$.

Let $B=b_1\times b_2\times b_3$
Let $B_i=B/b_i$
Then, $525=B_1,100=B_2,84=B_3$

Now I try and solve $(B_i)(X_i)≡ 1 \mod b_i$

I can see that $(B_1)(X_1)≡ 1 \mod b_1 $yields $525(X_1)≡ 1 \mod 4 $with$ X_1 $being $1$.
For $(B_2)(X_2)≡ 1 \mod b_2$, I get $100(X_2)≡ 1 \mod 21$. $X_2$ turns out to be $-1$.
For $(B_3)(X_3)≡ 1 \mod b_3 = 84(X_3)≡ 1 \mod 25$, I needed to use the extended euclidean algorithm to find the gcd and $X_3$, which turned out to be $-11$.

Work:

$$m \;n \; q \; r$$
$$\\84\;25 \;3 \;9$$
$$\\25 \;9 \;2 \;7$$
$$\\9 \;7 \;1\; 2$$
$$\\7 \; 2 \;3 \;1$$

$1=7-(3\times2)
\\=7-(3(9-7))=(4\times7)-(9\times3)
\\=(4(25-(9\times2)))-(9\times3)=(4\times25)-(9\times-11)
\\=(4\times25)-(11(84-(25\times3)))=(37\times25)-(11\times84)$

Thus, $X_3=-11$

It turns out that I computed the wrong $(X_2)$, it is instead $4$.

With this, I can compute the correct $Z$ such that it will satisfy the three congruence equations.

$Z=(3\times525\times1)+(100\times5\times4)+(84\times7\times-11)=-2893$
Using a calculator, I found that

$$Z \equiv 3 \pmod{4}$$
$$Z \equiv 5 \pmod{21}$$
$$Z \equiv 7 \pmod{25}$$

Best Answer

Generally it is easier to solve them a pair at a time, as follows.

${\rm mod}\ 25\!:\,\ 7\equiv x\iff x = 7+25j\,$ for some integer $j$

${\rm mod}\ 21\!:\,\ 5 \equiv x\equiv 7+25j\equiv 7+4j\!\iff\! 4j\equiv -2\!\iff\! 2j \equiv -1\equiv 20 \!\iff\! j \equiv \color{#c00}{10}$

$\qquad\quad\, \iff x = 7+25(\color{#c00}{10}+21k) = 257 + 525k$

${\rm mod}\,\ 4\!:\,\ 3 \equiv x = 257+525k\equiv 1+k\iff k \equiv \color{#0a0}2$

$\qquad\ \ \iff x = 257 + 525(\color{#0a0}2 + 4n) \equiv 1307\pmod{\!2100}$

Remark $ $ Only very small numbers were involved because we solved the congruences with largest moduli first, so that, in the end, when the numbers are bigger, this is compensated by computing at smaller moduli.

This method also works even if the moduli are not pairwise coprime, though in this general case there may be zero or multiple solutions. Furthermore it leads to the well-known criterion for existence of a solution in the general case - which characterizes the ubiquitous Prüfer domains. They generalize many common number systems and are characterized by a remarkably huge number of interesting properties, e.g. Gauss's Lemma for contents, lcm distributes over gcd (and reversely), contains = divides for fin. gen. ideals, etc. Thus it is well-worth investing the small effort needed to master this viewpoint of CRT.

Related Question