Find general solution of linear congruence equation

Question

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}$

Answer 1

The important properties of congruences are

1. if $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$ then $a+c\equiv b+d\pmod{n}$;
2. 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}$.