Congruence equation doubt

Question

Given the congruence equation:

$$70x\equiv 36 \pmod{198}$$

I have to find the smallest positive solution. I solved this by attempts (dividing the multiples of $70$ by $198$ and checking if the remainder is $36$) and I've got $x=9$ as a solution. Is my method incorrect?

Answer 1

$$70x-36 = 198k$$

Divide it $2$,

$$35x-18=99k$$

We want to find the smallest positive integer $x$ such that an integer $k$ exists.

I would be great if we can find $35^{-1} \pmod{99}$, we know it exists since $35$ and $99$ are corprime.

Let's use Euclidean algorithm: \begin{align}99&=2(35)+29\\ 35&=1(29)+6\\ 29&=4(6)+5\\ 6&=1(5)+1 \end{align}

Hence \begin{align} 1&=6-1(5)\\ &=6-(29-4(6))\\ &=5(6)-29 \\ &=5(35-29)-29\\ &=5(35)-6(29) \\ &=5(35)-6(99-2(35)) \\ &=17(35)-6(99) \end{align}

Hence $$17(35) \equiv 1 \pmod{99}$$

Our goal was to solve for $$35x \equiv 18 \pmod{99}$$

Multiply both sides by $17$, we have $$x \equiv 18(17) \pmod{99}$$

$$x \equiv 306 \equiv 3(99+1)+6\equiv 9 \pmod{99}$$

Hence the smallest positive solution is $9$.

Answer 2

Here is how the extended Euclidean algorithm runs to find directly the inverse of $35$ modulo $99$ (without having to work backwards): $$\begin{array}{rrrr} r-i&u_i&v_i&q_i\\ \hline 99&0&1\\ 35&1&0&2 \\ \hline 29&-2&1&1\\6&3&-1&4\\ 5&-14&5&1\\1&\color{red}{17}&-6\\ \hline \end{array}$$ so $$35x\equiv 18\mod 99\iff x\equiv 35^{-1}\cdot 18\equiv17\cdot 18\equiv 9\mod 99.$$

Answer 3

That's not really the right method, I'm sorry to say.

If $70x \equiv 36 \bmod 198$, then $70x - 36$ is a multiple of $198$. In symbols: $70x-36=198k$ for some integer $k$. This equation has a common factor of $2$ for all $k$, so we divide by $2$ to get $35x-18=99k$. There are no common factors now, so we can't simplify further.

$$70x \equiv 36 \bmod 198 \iff 35x \equiv 18 \bmod 99$$

You want to look for the "multiplicative inverse" of $35$, modulo $99$.

That means, find the smallest number $m$, where $35m \equiv 1 \bmod 99$.

First, notice that $35 = 5 \cdot 7$ and $99 = 3^2 \cdot 11$, and so $\gcd(35,99)=1$. The Chinese Remainder Theorem tells is that there are integers, $r$ and $s$, for which $35r+99s=1$.

The usual method to find $r$ and $s$ is to use repeated row operations:

$$\left(\begin{array}{cc|c} 1 & 0 & 35 \\ 0 & 1 & 99 \end{array}\right) \longrightarrow \left(\begin{array}{cc|c} 17 & -6 & 1 \\ -14 & 5 & 5 \end{array}\right)$$

This tells me that $r=17$ and $s=-6$, i.e. $17\cdot 35 + (-6)\cdot 99 = 1$. Reducing this equation modulo $99$ gives

\begin{eqnarray*} 17\cdot 35 + (-6)\cdot 99 &=& 1 \\ \\ [17\cdot 35 + (-6)\cdot 99] \bmod 99 &\equiv& [1 ]\bmod 99 \\ \\ [17 \cdot 35] \bmod 99 &\equiv & 1 \bmod 99 \end{eqnarray*}

This tells me that $17$ is the multiplicative inverse of $35$, modulo $99$, i.e. $17\cdot 35 \equiv 1 \bmod 99$.

I'm now in a place to solve this congruence:

\begin{eqnarray*} 35x &\equiv& 18 \bmod 99 \\ \\ {\color{red}{17\cdot}}\, 35x &\equiv& {\color{red}{17\cdot}} \, 18 \bmod 99 \\ \\ 1x &\equiv& 306 \bmod 99 \\ \\ x &\equiv& 9 \bmod 99 \end{eqnarray*}

All solutions are given by numbers that are $9$ more that a multiple of $99$, i.e.

$$x \in \{ 9 + 99k : k \in \mathbb Z \}$$

It seems that $x=9$ is the smallest solution, but a trial and error method will not work for very large numbers. Never mind simultaneous congruences!

Answer 4

Bezout's lemma says we can solve for $70a - 198b = 2$.

So I'd do that using a modified version Euclid's algorithm and common sense:

$70a - 198b = 2$

$35a - 99b = 1$

$99 = 2*35 + 29; 29= 99 - 2*35;$

$35 = 29 + 6; 6 = 35 - 29 = 35 - (99-2*35) = 3*35-99$

$29 = 4*6 + 5; 5 = 29 - 4*6 = (99-2*35) - 4(3*35-99) = 5*99 -14*35$

$6 = 5+1; 1 = 6-5 = (3*35-99)-(5*99 -14*35) = 35*17-6*99$

So $70*17 - 198*6 = 2$.

So $70*17\equiv 2 \mod 198$.

So $70*(17*18) \equiv 2*18 \equiv 36 \mod 198$

So $x = 17*18 = 306 \equiv 108 \mod 198$ is a solution. But is it the smallest solution?

Notice $70x \equiv 36 \mod 108\implies 70x = 36 + 198k \implies 35x = 18 + 99k \implies 35x \equiv 18\mod 99$

And we solve $x=108$ is a solution so $x \equiv 108\mod 99$ is also a solution. so $x = 9$ is the smallest solution.