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

  • $\begingroup$ 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$. $\endgroup$ – lulu Nov 12 '20 at 11:38
  • $\begingroup$ @lulu I think you mean, multiply both sides by $7$. $\endgroup$ – Gerry Myerson Nov 12 '20 at 12:28
  • $\begingroup$ @GerryMyerson Absolutely, thanks. $\endgroup$ – lulu Nov 12 '20 at 12:29
  • $\begingroup$ Your question is far too broad, and the example is far too specific. Please be more precise about what you don't understand. $\endgroup$ – 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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.