Finding the solution of the congruence $4x\equiv16\pmod{26}$ Solve the congruence 
$$4x\equiv16\mod{26}.$$
How do I find the solution to this? I have tried by the euclidean algorithm but the gcd is not $1$ so it doesn't work.
$$\begin{align}
26&=&6&\times4&+2\\
4&=&2&\times2&+0
\end{align}$$
Note: I understand we can see that $4$ and $17$ are solutions but how would I work this out algorithmically?
 A: While solving congruences, it is better to convert the congruence into the division algorithm form and then go for solving.
$4x \equiv 16 \pmod{26} \Rightarrow 26 \: | \: 4x-16$
It finally reduces down to $13 \: | \: 2(x-4) \Rightarrow 13 \: | \: (x-4)$.
By Euclidean algorithm, we have unique integer $k$ such that $x-4=13k$.
So required solution is $\color{red}{x=13k+4} \:, \:\color{blue}{k \in \mathbb{Z}}$ 
A: The relation can be "translated" into: $$26\mid 4x-16$$ or equivalently $$4x=16+26k\text{ for }k\in\mathbb Z$$ Dividing both sides by factor $2$ results in $$2x=8+13k\text{ for }k\in\mathbb Z$$
Evidently there will be solutions for $x\in\mathbb Z$ if and only if $k$ is even. 
Stating $k=2m$ we first find: $$2x=8+26m\text{ for }m\in\mathbb Z$$Dividing both sides by factor $2$ again we end up with:$$x=4+13m\text{ for }m\in\mathbb Z$$
A: You have to reduce factors, first. $26$ and $4$ are not relatively prime, but their common factor divides $16$, so you can solve $2x\equiv 8\pmod {13}$.
More generally, if you want to solve $ax\equiv b\pmod{d}$, you need $\gcd(a,d)$ to be a factor of $b$ (or else there are no solutions) and then divide $\gcd(a,d)$ from all of them to get an equation:
$$\frac{a}{\gcd(a,d)}x\equiv \frac{b}{\gcd(a,d)}\pmod{\frac{d}{\gcd(a,d)}}$$
A: In your question you have done extended Euclidean algorithm with $26$ and $4$. From this you can see that $\gcd(4,26)=2$ and you can also get
$$2=4\cdot(-6)+26\cdot1$$
meaning that
$$4\cdot(-6)\equiv 2\pmod{26}.$$
Now you can simply multiply both sides by $16/2=8$ to get
\begin{gather*}
4\cdot(-48)\equiv 16\pmod{26}\\
4\cdot4\equiv 4\pmod{26}
\end{gather*}
This gives you one solution $x_0=4$. (Of course, you could have easily guessed this solution, since $4\cdot4=16$. But the above also describes an algorithm how to arrive to the solution.)
However, you probably want to find all solutions. In general, $ax\equiv b\pmod n$ has solution only if $d\mid b$ where $d=\gcd(a,b)$. And if you have one solution $x_0$, all solutions can be expressed as $x=x_0+k\frac nd$ where $k\in\mathbb Z$.
In you case $n/d=26/2=13$, so the remaining solutions will differ from the one we have found by multiples of $13$.
So if we look at the congruence classes modulo $26$, all solutions are $x\equiv 4\pmod{26}$ and $x\equiv17\pmod{26}$. (In general we have $d$ congruence classes which solve the given linear congruence.) 
