3
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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$. $\endgroup$ – lulu May 28 '20 at 20:32
  • $\begingroup$ 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$..... $\endgroup$ – fleablood May 28 '20 at 21:27
  • 1
    $\begingroup$ ... 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$. $\endgroup$ – fleablood May 28 '20 at 21:32
  • $\begingroup$ 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. $\endgroup$ – fleablood May 28 '20 at 23:28
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ $69\cong\color{red}{0}\pmod3$. $\endgroup$ – user403337 May 28 '20 at 22:46
  • $\begingroup$ Well, that's a boner! Lessee.... A simple arithmetic mistake somewhere.... $\endgroup$ – fleablood May 28 '20 at 22:58
  • $\begingroup$ 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}$. $\endgroup$ – fleablood May 28 '20 at 23:09
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What’s happening after $k \equiv \frac{-2}{7}$, how did you get the congurence $k \equiv \frac{-2}{7-5}$? $\endgroup$ – user745970 May 28 '20 at 21:17
  • $\begingroup$ $\ k\equiv \frac{-2}{7}\ \Leftrightarrow 7k \equiv -2 \Leftrightarrow (7k-5k) \equiv -2 \Leftrightarrow k \equiv \frac{-2}{7-5}$ in modulo $5$ $\endgroup$ – Taha Direk May 28 '20 at 21:30
  • $\begingroup$ $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.) $\endgroup$ – fleablood May 28 '20 at 21:37
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy