# Find all solutions using the Chinese Remainder Theorem

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

• You need to clean this up a bit (I simply created a space between the three equations). Read what you've posted, as it renders on this site. Would you be able to make sense of things? For example, do you see: "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*2) 1=7-(3(9-7))=(4*7)-(9*3) 1=(4(25-(9*2)))-(9*3)=(4*25)-(9*-11) 1=(4*25)-(11(84-(25*3)))=(37*25)-(11*84) Thus, X_3=-11" – amWhy Feb 17 '17 at 21:46
• I find it difficult to understand exactly what you are doing. In your shoes, though, I would first solve $$\begin{cases} x \equiv 3 \pmod 4\\ x \equiv 5 \pmod {21}\\ \end{cases}$$ to get $$x \equiv A \pmod{84}$$ for some $A$, and then solve $$\begin{cases} x \equiv A \pmod{84}\\ x \equiv 7 \pmod {25}\\ \end{cases}$$ – Andreas Caranti Feb 17 '17 at 21:56
• It seems to me that you are relying too much on formulas, whereas here an algorithm would probably serve you better. – Andreas Caranti Feb 17 '17 at 21:57

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.

• Thank you, I will attempt using your method to solve the system of equations. – Arandomuser Feb 17 '17 at 23:32

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

• So, in essence, you're solving the first two equations and getting an x such that it satisfies both equations. Then you solve the final equation with your previous x equation, yielding you an answer to all three. Did I understand your reasoning correctly? Also, don't worry about it, it's written clearly enough to be read. – Arandomuser Feb 17 '17 at 23:35
• Yes, that's correct, we incrementally solve the system, moving to larger modulus values. If there is an "easy win", like two modular equivalences to the same value, take it! [Example: $x \equiv 11 \bmod 49$ and $x \equiv 11 \bmod 61$ instantly gives $x\equiv 11 \bmod 2989$] – Joffan Feb 18 '17 at 0:14
• @Arandomuser To clarify, this is the same method I used (except I showed all work - perhaps too much). However, I chose an order that generally minimizes the need to compute inverses of large numbers - see the Remark in my answer. – Bill Dubuque Feb 18 '17 at 0:17
• @Joffan No rebuke intended - just modular enlightenment. – Bill Dubuque Feb 18 '17 at 0:19

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}