# Solving system of congurences with the Chinese Remainder Theorem

Solve the system of congruences $$\begin{cases} x \equiv 1\ (\textrm{mod}\ 3) \\ x \equiv 4\ (\textrm{mod}\ 5) \\ x \equiv 6\ (\textrm{mod}\ 7)\end{cases}$$

I'm trying to learn about the Chinese Remainder Theorem and tried some problems as this.

I started with $$x \equiv 6\ (\textrm{mod}\ 7)$$ implying that $$x=7k+6$$ for some $$k$$. Then substituting this for $$x \equiv 4\ (\textrm{mod}\ 5)$$ I would get $$7k+6 \equiv 4\ (\textrm{mod}\ 5)$$. However here I got stuck, the proposed solution stated that I would have to solve

$$7k+6 \equiv 4\ (\textrm{mod}\ 5)$$

for $$k$$ and that it would result in $$k\equiv 4\ (\textrm{mod}\ 5).$$ I don't see how this would be possible. Solving $$7k+6 \equiv 4\ (\textrm{mod}\ 5)$$ for $$k$$ would result in $$k\equiv \frac{-2}{7}\ (\textrm{mod}\ 5)$$?

• Hint: $7\times 3\equiv 1 \pmod 5$ so just multiply your congruence by $3$. In other words, instead of dividing by $7$ multiply by the multiplicative inverse of $7$. – lulu May 28 '20 at 20:32
• Second hint: $7k\equiv 2k$ and $6\equiv 1 \pmod 5$ so you want to solve $2k+1\equiv 4 \pmod 5$. that means $2k \equiv 3\pmod 5$ and we can't divide but we can multiply... Not $2\times 3 \equiv 1 \pmod 5$ so we can multiply both sides by $3$ to be $6k \equiv 9\pmod 5$..... – fleablood May 28 '20 at 21:27
• ... the idea you want to get it the idea of a multiplicative inverse. It isn't the fraction $\frac 17$. But is the congruency class of integers, $a$ where $7a \equiv 1 \pmod 5$. Some experimenting and that if $a \equiv 3\pmod 5$ then $7a \equiv 21 \equiv 1 \pmod 5$. so the multiplicative invers is $3$. And we can write this as $\frac 17 \equiv 3 \pmod 5$ but we MUST be aware that "$\frac 17$" is NOT a fraction. It is the set of INTEGERS $\{.....,-7,-2,3,8, 13,....\}$ all of whic are $a \equiv 3\pmod 5$ and have the property $7a \equiv 1\pmod 5$. – fleablood May 28 '20 at 21:32
• I've added a long addendum to my answer showing how to find multiplicative inverses. It's actually probably more important than my actual answer. – fleablood May 28 '20 at 23:28

I like to use Bezout coefficients and isomorphisms as in the Chinese remainder theorem.

$$-3\cdot3+2\cdot5=1$$. Thus for the first two we get $$x\cong -9\cdot4+10\cdot1\cong{-26}\cong4\pmod{15}$$.

Then $$1\cdot15-2\cdot7=1$$.

So $$x\cong15\cdot6-14\cdot4\cong34\pmod{105}$$.

Well. $$x \equiv 1\pmod 3$$ so $$x \equiv 1 + 3j\pmod 105$$ and so one of the following is true $$x \equiv 1,4, 7,11, .......88,91,94,97,100,103 \pmod {105}$$ and

And $$x \equiv 4\pmod 5$$ so one of the following is true $$x \equiv 4,9,13,17,......86,91 ,96,101 \pmod {105}$$ and

And $$x \equiv 6\pmod 7$$ so one of the following is true $$x \equiv 6,13,20,27,..... 83,90,97, 104 \pmod 7$$.

According to the chinese remainder theorem there is exact one value $$\pmod {105}$$ that fits into all three of those.

So lets find it: You figured if $$x = 7k + 6 \equiv 4 \pmod 5$$.

So that means $$7k +6 \equiv 2k + 1 \equiv 4 \pmod 5$$ so $$2k \equiv 3\pmod 5$$. Now note that $$3*2 \equiv 6 \equiv 1 \pmod 5$$ so that means $$2k \equiv 3\pmod 5$$ so $$3*2k\equiv 3*3\pmod 5$$ so $$6k\equiv 9\pmod 5$$ and $$k \equiv 4 \pmod 5$$.

So have $$k = 5m + 4$$ for some $$m$$ and $$x = 7(5m + 4) + 6 = 35m +34$$ so $$x\equiv 34 \pmod {35}$$.

In hindsight this makes a lot of sense! $$x \equiv 4\equiv -1 \pmod 5$$ and $$x \equiv 6\equiv -1 \pmod 5$$. So $$x \equiv -1$$ both $$\pmod 5$$ and $$\pmod 7$$ and so $$x \equiv -1 \equiv 34 \pmod {35}$$ is a solution $$\pmod {35}$$ (and by CRT it is the only solution. It would have been much easier to do it that way).

Okay.... so we have $$x \equiv 34 \equiv -1\pmod {35}$$. Let's not make the same mistake twice. Let's use $$x = 35m -1$$ for some $$m$$.

SO $$35m -1 \equiv 1 \pmod 3$$ so $$35m \equiv 2\pmod 3$$. But $$35m\equiv 2m\equiv 2\pmod 3$$.

DON'T divide both sides by $$2$$. Division doesn't hold by modulo arithmetic (unless you are able and argue conditions of when terms and moduli are relatively primes). But multiplication does

So $$2m\equiv 2\pmod 3$$ so $$2*2m \equiv 2*2 \pmod 3$$ so $$4m \equiv 4 \pmod 3$$ and $$4m\equiv m \equiv 4 \equiv 1\pmod 3$$.

So there is an $$n$$ so that $$m = 3n + 1$$.

So $$x = 35(3n+1) -1= 105m + 34$$ so $$x \equiv 34\pmod{105}$$ is the final answer.

Which we probably should have seen when we got $$x \equiv 34\pmod {105}$$. As $$34 \equiv 1 \pmod 3$$ we could have realized we were done.

Oh well, hindsite is 20-20.

========

Well, to get to your REAL question.

How do we do multiplicative inverse?

If $$\gcd(n,k) =1$$ there is always an INTEGER $$k^{-1}$$ where $$k^{-1}k\equiv 1\pmod n$$.

So if you need to solve $$kx + a \equiv b\pmod n$$ you do

$$kx \equiv b-a \pmod n$$

$$k^{-1}kx \equiv k^{-1}(b-a)\pmod n$$

$$x \equiv k^{-1}(b-a)\pmod n$$.

Note: This is NOT division. It is multiplication by the multiplicative inverse.

SO if $$7k +6 \equiv 4\pmod 5$$ the

$$k \equiv 7^{-1}(4-6)\equiv 7^{-1}(-2)\pmod 5$$.

So what is $$7^{-1}\pmod 5$$?

Well by trial and error we can see $$3\cdot 7=21\equiv 1 \pmod 5$$ so $$7^{-1} \equiv 3 \pmod 5$$.

But more rigorously we can use Euclid's algorithm.

If $$7^{-1} \equiv a\pmod 5$$ then

$$7a \equiv 1 \pmod 5$$. So there is an $$m$$ so that $$7a = 1 - 5m$$ and

$$7a + 5m = 1$$. Let's find $$a$$.

$$7 = 5+ 2$$

$$5 = 2*2 + 1$$

So $$1 = 5 - 2*2$$.

$$2 = 7- 5$$ so

$$1 = 5 - 2(7-5)= 3*5-2*7$$

So $$m=3$$ and $$a=-2$$ is one solution. So $$7^{-1} \equiv -2 \pmod 5$$.

And $$7\cdot (-2) \equiv -14 \equiv 1 \pmod 5$$.

Well.... I got the negative value. That's okay. We can just add $$5$$....

$$1 = 3*5-2*7 = (3*5 - 7*5) + (-2*7 + 5*7) =-4*5 + 3*7$$.

So $$m =-4$$ and $$a=3$$ is another solution. And $$7^{-1} \equiv 3\equiv -2 \pmod 5$$.

And $$7\cdot 3 \equiv 21 \equiv 1 \pmod 5$$

So if $$7k+6 \equiv 4\pmod 5$$ then

$$7k \equiv -2 \pmod 5$$ and

$$3*7k\equiv 3*(-2)\pmod 5$$ and

$$k \equiv -6\equiv -1\equiv 4\pmod 5$$

• $69\cong\color{red}{0}\pmod3$. – user403337 May 28 '20 at 22:46
• Well, that's a boner! Lessee.... A simple arithmetic mistake somewhere.... – fleablood May 28 '20 at 22:58
• Yes, when I chose to do $x = 35m -1$ rather than $x = 35m + 34$, I shouldn't have gone back to $x=35m+34$. Had I done $x=35m + 34$ in the first place I'd have gotten $2m+1\equiv 1\pmod 3$ so $2m\equiv 0$ so $3*2m=6m\equiv m \equiv 2*0=0\pmod 3$ and so $m = 3n$ and I'd have $x = 35(3*n)+34=105n + 34 \equiv 34 \pmod {105}$. – fleablood May 28 '20 at 23:09

Yes it results , and $$\ k\equiv \frac{-2}{7}\ \equiv \frac{-2}{7-5}\ =-1 \equiv 4\ (\textrm{mod}\ 5)$$

So, $$x \equiv 34\ (\textrm{mod}\ 35)$$

Also, $$x \equiv 1\ \equiv 34\ (\textrm{mod}\ 3)$$

Hence, $$x \equiv 34\ (\textrm{mod}\ 105)$$

• What’s happening after $k \equiv \frac{-2}{7}$, how did you get the congurence $k \equiv \frac{-2}{7-5}$? – user745970 May 28 '20 at 21:17
• $\ k\equiv \frac{-2}{7}\ \Leftrightarrow 7k \equiv -2 \Leftrightarrow (7k-5k) \equiv -2 \Leftrightarrow k \equiv \frac{-2}{7-5}$ in modulo $5$ – Taha Direk May 28 '20 at 21:30
• $5 \equiv 0\pmod 5$ so $7\equiv 7-5\pmod 5$. So if we are allowed to talk about fractions if we can say $\frac 17 \pmod 5$ makes any sense, we can so $\frac 1{7}\equiv \frac 1{7 \pm 5k} \pmod 5$ so $\frac 17 \equiv \frac 12 \pmod 5$. !!!!IF!!!! we are allowed to say any of that and if any of that makes any sense. ... (IMO I don't like this answer as it avoids the issue of whether $\frac 17 \pmod 5$ does make any sense. (Which is does but it requires a lot of explanation.) – fleablood May 28 '20 at 21:37

If you're not a fan of substituting in modular arithmetic, there is an explicit way of solving these kinds of problems, which goes like this: given the system $$\begin{cases} x \equiv a_1\ (\textrm{mod}\ m_1) \\ \quad \vdots \\ x \equiv a_r\ (\textrm{mod}\ m_r) \end{cases}$$ Define the full modulus $$M=\prod^{r}_{i=1} m_i$$ and the reduced modulus $$M_i=M/m_i$$, then the solution is $$x=\sum^r_{i=1}a_iM_iN_i\qquad(\!\!\!\!\!\mod\!\!M)$$ where $$N_iM_i=1\;(\!\!\!\mod m_i)$$ $$-$$ or, in plain English, the $$N_i$$ are the inverses to the reduced moduli $$M_i$$ in modulo $$m_i$$, which you can find either by trial-and-error or by using the Euclidean algorithm.

This shifts the weight from solving modular equations to calculating a few products, using the Euclidean algorithm $$r$$ times, and doing some addition at the end.