# Find All Solutions to System of Congruence

$$\begin{cases} x\equiv 2 \pmod{3}\\ x\equiv 1 \pmod{4}\\ x\equiv 3 \pmod{5} \end{cases}$$

$n_1=3\\ n_2=4\\ n_3=5\\ N=n_1 * n_2 * n_3 =60\\ m_1 = 60/3 = 20\\ m_2 = 60/4 = 15\\ m_3 = 60/5 = 12\\ gcd(20,3)=1=-20*1+3*7\\ gcd(15,4)=1=-15*1+4*4\\ gcd(12,5)=1=12*3-5*7\\ x=-20*2-15*1+12*3\equiv -19 \equiv 41 \pmod{60}\\$

The above is what I've tried so far. Can someone tell me where I'm going wrong? It's my first time doing this and looking at the explanation and examples for the Chinese Remainder Theorem makes my head want to explode.

• It's much simpler if you solve them two-at-a-time, e.g. see here. If you are interested I can show you how. Commented Mar 28, 2015 at 4:00
• @BillDubuque: I'd be very grateful if you'd show me how!
– Bob
Commented Mar 28, 2015 at 4:31
• Ok, see my answer. Commented Mar 28, 2015 at 4:57

It's usually easier to solve the congruences successively, i.e. a pair at a time, replacing a pair of congruences by their solution's congruence. So we take a general solution of the first congruence, substitute it into the second, solve that, then substitute that solution into the third, etc, continually replacing (e.g. top) $$\,2\,$$ congruences by an equivalent congruence, e.g. as below

\qquad\quad\begin{align} x\equiv \color{#0a0}3\!\!\!\pmod{\! \color{#0a0}5}\\ x\equiv \color{#0a0}1\!\!\!\pmod{\! \color{#0a0}4}\\ x\equiv 2\!\!\!\pmod{\! 3}\end{align}\! \iff \begin{align} \\ x\equiv \color{#0a0}{13}\!\!\!\pmod{\!\color{#0a0}{20}}\\ x\equiv \ \ 2 \!\!\!\pmod{\!3} \ \ \end{align}\!\! \begin{align} \\ \\ \iff x\equiv \color{#c00}{53}\!\!\!\pmod{\!60}\end{align}

Below is the congruence arithmetic justifying the above equivalences.

$${\rm mod}\ 5\!:\,\ 3\equiv x\iff x = \color{#90f}{3\! +\! 5\:\!j}.\,$$ Substituting this value of $$\,x\,$$ in the 2nd congruence we get

$${\rm mod}\ 4\!:\,\ 1\equiv x = \color{#90f}{3\!+\!5\:\!j}\equiv -1\!+\!j\iff j\equiv 2\iff \color{#0a0}{j=2\!+\!4k}$$

Thus the first $$2$$ congruence are equivalent to $$\,x = \color{#90f}{3\!+\!5}\:\!\color{#0a0}j \equiv \color{#0a0}{13\!+\!20k}.\,$$ Again, substituting this value of $$\,x\,$$ into the 3rd congruence yields

$${\rm mod}\ 3\!:\,\ 2\equiv x = \color{#0a0}{13+20k}\equiv 1\!-\!k\iff k\equiv 2\iff \color{#c00}{k=2\!+\!3n}$$

Therefore the $$3$$ congruences are equivalent to $$\,x = \color{#0a0}{13\!+\!20}\:\!\color{#c00}k = \color{#c00}{53+60n}$$

Remark  Below is a summary of the reduction of the top two congruences:

\qquad \begin{align} x\equiv 3\!\!\!\pmod{\! 5}\\ x\equiv 1\!\!\!\pmod {\!4}\end{align} \iff \begin{align} x = \color{#90f}{3\! +\! 5\color{#0a0}j}\\ \color{#0a0}{j=2\!+\!4k}\end{align} $$\iff x =\color{#90f}{3\!+\!5}(\color{#0a0}{2\!+\!4k})\overbrace{= \color{#0a0}{13+20k}}^{\large\,\ \equiv\ \ \color{#0a0}{13}\!\pmod{\!\color{#0a0}{\!\!20}}\!}$$

Note that all reductions are $$\iff$$ i.e. "if and only if", i.e. equivalences, because we desire to replace two congruences by an equivalent congruence. This means each reduction step must be reversible. In particular, this means that if we encounter a congruence of the form $$\,ac\, x\equiv bc\pmod{\!mc}\,$$ then any cancelling of $$\,c\neq 0\,$$ must also be done to the modulus, i.e.

$$a\color{#c00}c\,x\equiv b\color{#c00}c\!\!\!\pmod{m\color{#c00}c}\iff mc\mid (ax\!-\!b)c \iff m\mid ax\!-\!b\iff ax\equiv b\!\!\!\pmod m$$

i.e. we must cancel $$\,\color{#c00}{c\,\ \rm everywhere}\,$$ (compare here for a fractional view of this). Such cancellations occur frequently in the general case when the moduli are not pair-coprime.

Notice we ordered the congruences by largest-moduli-first, so that when the numbers are bigger near the end, the moduli are smaller, so modular arithmetic is easier. This optimization pays off much more when larger moduli are present.

See here for a general formula (Easy CRT) for solving a pair of congruences, including the case of noncoprime moduli.

• What is that double-sided arrow? And thank you for the explanation!
– Bob
Commented Mar 28, 2015 at 5:06
• @Bob It means "if and only if" or "equivalently". I elaborated on this in a remark. Commented Mar 28, 2015 at 16:16

I think you're a bit confused about the recipe used to solve the system of congruences using the Chinese Remainder Theorem. Using your notation, the actual solution is given by \begin{align*} x = 2 \cdot m_1 \cdot ({m_1}^{-1} \text{ mod } 3) + 1 \cdot m_2 \cdot ({m_2}^{-1} \text{ mod } 4) + 3 \cdot m_3 \cdot ({m_3}^{-1} \text{ mod } 5) \, . \end{align*} Let's see why this answer works. Since $m_1$ is divisible by both $4$ and $5$, the first term is "invisible" when we consider $x$ mod $4$ and mod $5$: it is congruent to $0$ mod $4$ and mod $5$, so it doesn't contribute to the answer of the last two congruences. Thus, we can focus on making this first term satisfy the first congruence. Okay, so far we know the first term should have as factors $2$ (the congruence we want) and $m_1$ (to get rid of the effect mod $4$ and $5$). But now we don't satisfy the first congruence; the $m_1$ throws things off. To fix this, we multiply by the ${m_1}^{-1}$ mod $3$. Then mod $3$ we have \begin{align*} x &= 2 \cdot m_1 \cdot ({m_1}^{-1} \text{ mod } 3) + 1 \cdot m_2 \cdot ({m_2}^{-1} \text{ mod } 4) + 3 \cdot m_3 \cdot ({m_3}^{-1} \text{ mod } 5)\\ &\equiv 2 \cdot m_1 \cdot ({m_1}^{-1} \text{ mod } 3) \equiv 2 \pmod{3} \end{align*} as desired. Similar reasoning shows that $x$ satisfies the given congruences mod $4$ and $5$.

You have the right idea with your solution, but you're missing some factors. Since you've shown $1 = 20 \cdot (-1) + 3 \cdot 7 \equiv 20 \cdot (-1) \pmod{3}$, then $${m_1}^{-1} \text{ mod } 3 = 20^{-1} \text{ mod } 3 = -1 \equiv 2 \pmod{3} \, .$$ So the first term should be $2 \cdot 20 \cdot 2$. Can you figure out the other two terms now?

• Entirely possible and likely I'm confused. I was trying to use math.stackexchange.com/questions/79282/… as a template, since the most discussed similar problems linked there. Where should I go from here?
– Bob
Commented Mar 28, 2015 at 3:30
• I've added more explanation. Can you figure it out now? Commented Mar 28, 2015 at 3:37
• $second term: 1\cdot15\cdot3=45\\ third term: 3\cdot12\cdot3=108\\$
– Bob
Commented Mar 28, 2015 at 3:41
• Looks good to me! Now double check that your answer works, i.e., that it satisfies the given system of congruences. Commented Mar 28, 2015 at 3:42
• Seems to. $80+45+108 = 233\equiv 53 \pmod{60}$. Thanks a ton.
– Bob
Commented Mar 28, 2015 at 3:43

You did it well until the computation of $$x$$. You forgot to do the multiplication by $$3$$ in the last term: $$x=(-20*1)*2-(15*1)*1+(12*3)*3\equiv 53\pmod{60}$$