<s>[INST] 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?
 [/INST] $$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$.
</s>