<s>[INST] Solve $15\cdot x=27\pmod{18}$ EXERCISE:

Solve   $15\cdot x\equiv 27\pmod{18}$

SOLUTION:
We know that $\gcd(15,18)=3$ and $3\setminus 27=3\cdot 9$.
So from http://www.math.niu.edu/~richard/Math420/lin_cong.pdf we can conclude that we have 3 solutions!
Then we have that $15\cdot x\equiv 27\pmod{18}\implies 5\cdot x\equiv 9\pmod{6}$
So, from now and then I can't understand how to proceed!
The book continue with this:
"We have a unique solution of   $5\cdot x\equiv 9\pmod{6}$ which is":
$x=5\cdot 9 =45\equiv 3\pmod 6$ and $15\cdot 3\equiv 27\pmod{18}\equiv 9\pmod{18} $
The other solutions are:$(9,15)$. So all solutions are these: $(3,9,15)$
Can anyone explain me how the author of the book continue the exercise?I really can't understand how he ends up with these solutions!Is there another way to reach these solutions?
I would really appreciate a thorough  explanation, since I've just started working on these type of exercises and I have to clear my mind on them. 
Thanks for your time !
 [/INST] The primary task is finding $5^{-1}$ modulo $6$, because once we find it, we multiply both sides by it to make $x$ have coefficient $1$ (therefore determining $x$). In general, here's how to find $z^{-1}$ modulo $a$.


*

*Want to find $y$ such that $zy \equiv 1 \pmod{a}$

*This is equivalent to: find $y$ and $b$ (modulo $6$) such that $zy - 1 = ab$, i.e. $xy + a(-b) = 1$. Equivalently, want to find $y$ and $b$ such that $zy + ab = 1$. These exists because of Bézout.

*To find these, use the Euclidean algorithm as in the following examples.
$1)$ $z = 24$, $a = 7$. 
First divide $z$ by $a$: $24 = 3\cdot 7 + 3$. The quotient is $q_1 = 3$ and the remainder is $r_1 = 3$. Now divide $a$ by $r_1$: $7 = 2 \cdot 3 + 1$. Quotient is $q_2 = 2$ and remainder is $r_2 =1$. STOP (always stop when the remainder is $1$). Fill out a table.
$$\begin{array}{|c|c|} \hline y & b \\ \hline 1& 0\\ \hline 0 & 1 \\ \hline 1 & -3 \\ \hline -2 & 7 \\ \hline \end{array}$$
Here's how to fill out the table. Call $R_n$ the $n$th row. $R_1$ and $R_2$ are always as such. For $n\ge 3$, $R_n = R_{n-2} - q_{n-2} R_{n-1}$.
The last row has the numbers you want (so here, $y = -2$ and $b=7$).
$2)$ Your example ($a = 6$, $z = 5$).
$5 = 0\cdot 6 + 5$. So $q_1 = 0$ and $r_1 = 5$. Next $6 = 1\cdot 5 + 1$, so $r_2 = 1$ and $q_2 = 1$. STOP
$$\begin{array}{|c|c|} \hline y & b \\ \hline 1& 0\\ \hline 0 & 1 \\ \hline 1 & 0 \\ \hline -1 & 1 \\ \hline \end{array}$$
So $y = -1$ and $b = 1$.
$-1$ is $5$ modulo $6$. So $5^{-1}$ is $5$ modulo $6$. Now the author proceeds to find $x$ by multiplying both sides by $5$.
</s>