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

• With such small numbers, trial and error is very fast. Or you could note that $2\times 7\equiv 1 \pmod {13}$ and just multiply both sides of your congruence by $14$. – lulu Nov 12 '20 at 11:38
• @lulu I think you mean, multiply both sides by $7$. – Gerry Myerson Nov 12 '20 at 12:28
• @GerryMyerson Absolutely, thanks. – lulu Nov 12 '20 at 12:29
• Your question is far too broad, and the example is far too specific. Please be more precise about what you don't understand. – Bill Dubuque Nov 12 '20 at 12:39

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

• Thank you very much, but I don't get from this the general form. Is the general from the 2kx = 5k ? – kopkaa Nov 12 '20 at 15:55
• @kopkaa Sorry, but I can't understand. The general solution is $x\equiv9\pmod{13}$. – egreg Nov 12 '20 at 17:03