Solve the following congruence:
$19x\equiv 1\;(\text{mod}\;36)$
My work:
I found an inverse of $19$ and $36$ which is $9$.
$9\cdot 19x\equiv 9\cdot 1\;(\text{mod}\;36)$
$171x\equiv 9\;(\text{mod}\;36)$
$9x\equiv 9\;(\text{mod}\; 36)$
$x\equiv 1\;(\text{mod}\;4)$ is my final answer...
Is it correct?
On
We have that $19^2 = 361 = 36 \times 10 +1 \implies 19^2 \equiv 1 \pmod{36}$. Hence, $$x \equiv 19 \pmod{36}$$
On
Another approach, perhaps less "guessing":
$$19=3\pmod 4\;\;,\;\;19=1\pmod 9$$
$$3^{-1}=3\pmod 4\;\;,\;\;1^{-1}=1\pmod 9$$
thus
$$x=19^{-1}\pmod{36=4\cdot9}\iff x=1\pmod 4\;\;\wedge\;\;x=1\pmod9\iff$$
$$\iff x=3\pmod 4\;\;\wedge\;\;x=1\pmod 9\implies x=19\pmod{36}$$
For the last step you can use The Chinese Remainder Theorem, say (though here it is overkill)
Method $1:$
We need $x\equiv19^{-1}\pmod{36}$
Using Carmichael function $\lambda(36)=$lcm$(6,2)=6\implies a^6\equiv1\pmod{36}$ if $(a,6)=1$ $\implies$ord$_{36}(a)$ must divide $6$
$19^1\equiv19\pmod{36},19^2=361\equiv1\pmod{36}\implies 19\equiv19^{-1}\pmod{36}$
Method $2:$
Like this, expressing as Continued Fraction,
$$\frac{36}{19}=1+\frac{17}{19}=1+\frac1{\frac{19}{17}}=1+\frac1{1+\frac2{17}}=1+\frac1{1+\frac1{\frac{17}2}}=1+\frac1{1+\frac1{8+\frac12}}$$
The previous convergent of $\displaystyle\frac{36}{19}$ is $\displaystyle1+\frac1{1+\frac18}=\frac{17}9$
$\displaystyle\implies 36\cdot9-19\cdot17=1\implies-17\cdot19\equiv1\pmod{36}\implies 19^{-1}\equiv-17\equiv19$
Alternatively observe that the next convergent of $\displaystyle\frac{36}{19}$ is $\displaystyle1+\frac1{1+\frac1{8+\frac11}}=\frac{19}{10}$
$\displaystyle\implies 36\cdot10-19\cdot19=-1\implies-19\cdot19\equiv-1\pmod{36}\implies 19^{-1}\equiv19$
Method $3:$
We have $19x\equiv1\pmod{36}\ \ \ \ (1)$
As $36=9\cdot4$ with $(9,4)=1$
$\ \ \ \ (1)\implies 19x\equiv1\pmod9\implies x\equiv1\pmod 9$
$\ \ \ \ (1)\implies 19x\equiv1\pmod4\implies -x\equiv1\pmod 4\implies x\equiv-1\pmod 4$
Using well-known CRT, we can show $x\equiv19\pmod{36}$