Solving system of congurences with the Chinese Remainder Theorem

Question

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)$?

Answer 1

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

Answer 2

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.

Answer 3

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$

Answer 4

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