Solve for $n$, $5n\equiv 3 \pmod 8$

Question

I've tried it like this $5n≡3 \pmod 8$

$\implies 10n≡6 \pmod 8$

$\implies 2n≡6 \pmod 8$

$\implies n≡3 \pmod 4$

$\implies n=4a+3$

But when I put $a=0 \implies n=3$

putting it into the original condition we get $15≡3 \pmod 8$ which is false.

So, I'm wondering what is wrong in my solution.

Answer 1

The problem in your solution is that $5n\equiv 3 \pmod 8$ is not equivalent to $10n\equiv 6 \pmod 8$.

To solve this problems you would find invertible $mod\ 8$ such that when multiplied by $5$ let rest $1$ (in this case) and multiply the equation by it. For example, $5$ is invertible $mod\ 8$ and $$5.5=25\equiv 1\pmod8,$$ so we have $$n\equiv 25n\equiv 5.5n\equiv 5.3\equiv 15\equiv 7\pmod8.$$ Therefore $n=7+8k$ is solution of the equation for all integer $k$.

Answer 2

I'm not sure what's wrong with your solution since I don't quite understand it to begin with, but here is an alternative solution...

---

Consider the following cases:

• $n\equiv\color\red0\pmod8\implies5n\equiv5\cdot\color\red0\equiv0\pmod8$
• $n\equiv\color\red1\pmod8\implies5n\equiv5\cdot\color\red1\equiv5\pmod8$
• $n\equiv\color\red2\pmod8\implies5n\equiv5\cdot\color\red2\equiv2\pmod8$
• $n\equiv\color\red3\pmod8\implies5n\equiv5\cdot\color\red3\equiv7\pmod8$
• $n\equiv\color\red4\pmod8\implies5n\equiv5\cdot\color\red4\equiv4\pmod8$
• $n\equiv\color\red5\pmod8\implies5n\equiv5\cdot\color\red5\equiv1\pmod8$
• $n\equiv\color\red6\pmod8\implies5n\equiv5\cdot\color\red6\equiv6\pmod8$
• $n\equiv\color\red7\pmod8\implies5n\equiv5\cdot\color\red7\equiv3\pmod8$

Hence $5n\equiv3\pmod8 \iff n\equiv7\pmod8$.

Answer 3

The problem with your solution is that $5n\equiv 3\pmod{8}\implies 10n\equiv 6\pmod{8}$, but $10n\equiv 6\pmod{8}\not\implies 5n\equiv 3\pmod{8}$.

For a proof that $n=4a+3$ generates all the solutions you would want to have $\iff$ after every equivalence.

Here's a correct solution.

$$5n\equiv 3\equiv -5\pmod{8}$$

$$\stackrel{:5}\iff n\equiv -1\equiv 7\pmod{8}$$

because $\gcd(5,8)=1$. All the solutions are generated by $n\equiv 7\pmod{8}$.

Answer 4

As $5$ and $8$ are coprime there is a single congruence class of solutions; namely $[n]=[7]$ mod $(8)$ in this case, and so $5\times7=35\equiv3\pmod{8}$. You can find the answer by trial multiplication of all numbers from $0$ to $7$ with $5$ until you hit residue $3$ in the congruence. Your answer goes wrong when you multiply by $2$ to get $10n\equiv6\pmod{8}$; this congruence equation now has two congruence classes of solutions, namely $[n]=[3]$ and $[n]=[7]$ mod $(8)$ and so you cannot find the unique congruence class solution for your original equation from here on. Sure you can simplify to $2n\equiv6\pmod{8}$, but you still have $[n]=[3]$ and $[n]=[7]$ mod $(8)$ as solutions; then dividing through by $2$ to get $n\equiv3\pmod{4}$ gives you both solutions as one congruence class $[n]=[3]$ mod $(4)$, which is not what you want.

Answer 5

$5(4a+3) \equiv 3$ (mod $8$)

You haven't solved for $a$.

$20a + 15 \equiv 3$ (mod $8$)

$4a \equiv -12 \equiv 4$ (mod $8$)

$a \equiv 1$ (mod $8$)

$n \equiv 7$ (mod $8$)

---

The simplest trick is:

$5n \equiv 3$ (mod $8$)

$-3n \equiv 3$ (mod $8$)

$n \equiv -1$ (mod $8$)

$n \equiv 7$ (mod $8$)