How to find all $x\in\mathbb{Z}$ that satisfy this congruence modulo:
$15x\equiv 5 \mod25$.
So, I know that first thing I need to check is if $\gcd(a,m)$ is dividing $b$. In our case $a$ is $15$, $b$ is $5$ and $m$ is $25$, therefore $\gcd(15,25) = 5$. We see that our $b$ can be divided by $\gcd$, so we can divide whole congruence modulo with 5, and we get this:
$3x\equiv 1 \mod5$.
We can also write this as $3x + 5k = 1$.
After Euclid's algorithm and making the table, I get this.
$\begin{array}{|c|c|c|c|} \hline a_i&1& 0& 1& -1 \\ \hline b_i&0& 1& -1& 2\\ \hline q_i&& & 1& 1& 2\\ \hline &5& 3& 2& 1& 0\\ \hline \end{array}$
From this I am not sure how should I precede. I can confirm $3x + 5k = 1$ by putting last $a$ and $b$ instead of $k$ and $x$, but I really don't have idea what should I do next.
Any suggestion would be helpful.
Quite simple: $3$ is a unit mod. $5$ and its inverse is $2$, so $$3x\equiv 1\mod 5\iff2(3x)=(2\cdot 3)x\equiv x\equiv 2\mod 5.$$