Modular Arithmatic - Solving congruences

Question

I'm sure this is pretty basic but I'm struggling to understand how to go about solving this problem for my homework. The question states "Solve the following congruences for x". The first problem is $2x+1\equiv 4\pmod 5$.

Answer 1

Solve it like you would any linear equation expect you figure out what is $2^{-1}$ the multiplicative inverse of $2 \pmod 5$. That is find $a$ such that $2a \equiv 1 \pmod 5$.

Answer 2

By multiplaying with 3, we get: $$6x+3=12\mod 5,$$ from were is: $$x=9 \mod 5=4\mod 5$$.

Answer 3

There are many ways to solve the problem. The conceptually simplest, but most tedious, is to test one by one the possibilities $x\equiv 0\pmod{5}$, $x\equiv 1\pmod{5}$, and so on up to $x\equiv 4\pmod{5}$. Quickly we find that $x\equiv 4\pmod{5}$. (This approach would become quite unpleasant if $5$ were replaced by $97$.)

It is simpler to use some algebra. So rewrite as $2x\equiv 3\pmod{5}$. Since $3\equiv 8\pmod{5}$, it is convenient to rewrite the congruence as $2x\equiv 8\pmod{5}$. Then since $2$ and $5$ are relatively prime, we can divide by $2$, getting $x\equiv 4\pmod{5}$.

A fancier version is to start from $2x\equiv 3\pmod{5}$. Now multiply both sides by $3$ (the modular inverse of $2$). We get $6x\equiv 9\pmod{5}$. But $6\equiv 1\pmod{5}$ and $9\equiv 4\pmod{5}$, so we conclude that $x\equiv 4\pmod{5}$.

Remark: We used congruence notation throughout, since it is very important to get accustomed to it. But $2x\equiv 3\pmod{5}$ means that $5$ divides $2x-3$. So we want to solve $2x-3=5k$, that is, $2x=3+5k$. So we want to find a $k$ such that $3+5k$ is divisible by $2$. It is clear that $k=1$ works, giving $2x=8$ so $x=4$. Any number congruent to $4$ modulo $5$ will also work, giving answer $x\equiv 4\pmod{5}$.

Answer 4

Hint $\ {\rm mod}\,\ 2k\!-\!1\!:\,\ 2k\!-\!1\equiv 0\,\Rightarrow\, \color{#c00}{2k\equiv 1},\ $ so $\, k\equiv 2^{-1}.\,$ Therefore, as usual, we can solve

the linear equation $\ 2x\equiv b\ $ by scaling it by $\, 2^{-1}\equiv k\,$ to get $\, x\equiv (\color{#c00}{2k})x \equiv kb.$