Find general solution of linear congruence equation Congruences are beyond my understanding, I do not understand at all, if you could explain it to me as simply as possible on this example, I would be very grateful:
Find a general solution of linear congurence $2x\equiv 5 \pmod{13}$
 A: The important properties of congruences are

*

*if $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$ then $a+c\equiv b+d\pmod{n}$;

*if $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$ then $ac\equiv bd\pmod{n}$.

If $x$ is a solution to $2x\equiv5\pmod{13}$, then also
$$
2kx\equiv 5k\pmod{13}
$$
for every integer $k$, because $k\equiv k\pmod{13}$ and you can apply property 2.
How does this simplify the situation? Well, if you choose $k=7$, you get
$$
14x\equiv 35\pmod{13}
$$
and therefore
$$
x\equiv9\pmod{13}
$$
So if $x$ is a solution, then $x\equiv 9\pmod{13}$. But also the converse is true, because from $x\equiv 9\pmod{13}$ we obtain $2x\equiv18\equiv5\pmod{13}$.
In this case it is quite the same as solving a degree one equation: $2x=5$ becomes $x=5/2$ after multiplying both sides by $1/2$.
In the case of congruences we cannot “multiply by $1/2$”; but we can see that $\gcd(2,13)=1$, so by the general theory, we know there exists $k$ such that $2k\equiv1\pmod{13}$. It's just a matter of finding it.
Trial will work for small numbers, the extended Euclidean algorithm will do for bigger numbers.
When we have this $k$, then the congruence becomes
$$
2kx\equiv 5k\pmod{13}
$$
and so $x\equiv5k$. The steps can be done backwards, because upon multiplying this by $2$, the right-hand side becomes $5\cdot2k\equiv5\cdot1\equiv5\pmod{13}$.
