Congruence equation doubt 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?
 A: $$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$.
A: 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.$$
A: 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!
A: 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.
