Find all solutions using the Chinese Remainder Theorem

Question

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}$$

Answer 1

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.

Answer 2

You can work this stepwise by combining any two modular equivalence specifications and then combining the result with the third.

So the CRT-combined result for modulus $4$ and $21$ is:

$$\left . \begin{array}{rl} x &\!\equiv 3 \bmod{4}\\ x &\!\equiv 5 \bmod{21}\\ \end{array} \right \} \quad x\equiv 47 \bmod 84 $$

And there are a number of ways of getting there, but this example is a little too simple to show them to any advantage. By contrast the second combination:

$$\left . \begin{array}{rl} x &\!\equiv 47 \bmod 84\\ x &\!\equiv 7 \bmod 25\\ \end{array} \right \} \quad x\equiv 1307 \bmod 2100 $$

shows off nicely that given $84 \equiv 9 \bmod 25$, we can calculate $9^{-1} \equiv 14 \bmod 25$ and we need to get from $47 \equiv -3$ to $7 \bmod 25$, so $14(7--3) = 140 \equiv 15 \bmod 25$ gives us $47 + 15\cdot 84 = 1307 \bmod (84\cdot 25 = 2100)$ as our least answer.

Then of course the family of answers is $x=1307+2100k$.

Answer 3

I should at least mention that there is another way to solve

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

We need to find integers $\alpha,\beta, \gamma \in \mathbb Z_{2100}$ (where $2100 = 4 \cdot 21 \cdot 25$) such that

$\begin{cases} \alpha \equiv 1 \pmod{4}\\ \alpha \equiv 0 \pmod{21}\\ \alpha \equiv 0 \pmod{25} \end{cases}, \qquad \begin{cases} \beta \equiv 0 \pmod{4}\\ \beta \equiv 1 \pmod{21}\\ \beta \equiv 0 \pmod{25} \end{cases},\; \text{and} \qquad \begin{cases} \gamma \equiv 0 \pmod{4}\\ \gamma \equiv 0 \pmod{21}\\ \gamma \equiv 1 \pmod{25} \end{cases}$

It will follow that $x \equiv 3\alpha + 5 \beta + 7 \gamma \pmod{2100}$ where $2100 = 4 \cdot 21 \cdot 25$.

To solve $\begin{cases} \alpha \equiv 1 \pmod{4}\\ \alpha \equiv 0 \pmod{21}\\ \alpha \equiv 0 \pmod{25} \end{cases}$

we first note that $\alpha \equiv 0 \pmod{21}$ and $\alpha \equiv 0 \pmod{25}$ implies $\alpha \equiv 0 \pmod{525}$. So $\alpha = 525t$ for some integer $t$.

Thus \begin{align} \alpha \equiv 1 \pmod 4 &\implies 525t \equiv 1 \pmod 4 \\ &\implies t \equiv 1 \pmod 4 \\ &\implies \alpha \equiv 525 \pmod{2100} \end{align}.

Similarly \begin{align} \beta\equiv 1 \pmod{21} &\implies 100t \equiv 1 \pmod{21} \\ &\implies -5t \equiv 1 \pmod{21} \\ &\implies t \equiv 4 \pmod{21} \\ &\implies \beta \equiv -20 \pmod{2100} \end{align}

and \begin{align} \gamma \equiv 1 \pmod{25} &\implies 84t\equiv 1 \pmod{25} \\ &\implies 9t \equiv 1 \pmod{25} \\ &\implies t \equiv 14 \pmod{25} & (9 \cdot 14 = 126 \equiv 1 \pmod{25})\\ &\implies \gamma \equiv 1176 \pmod{2100} \end{align}.

So \begin{align} x &\equiv 3\alpha + 5 \beta + 7 \gamma \pmod{2100} \\ &\equiv 3(525) + 5(-20) + 7(1176) \pmod{2100} \\ &\equiv 1307 \pmod{2100} \\ \end{align}