# Find all solutions in modular arithmetic

I need to find all solutions to:

$$4x\equiv3\pmod7$$

I know the solutions are in $${0, 1, 2, 3, 4, 5, 6}$$ and I got $$x \equiv 6 \pmod7$$ so my answer was 6 but I don't know if that's all the answers.

I have the same problem with:

$$3x+1\equiv4\pmod5$$

I got $$x\equiv1\pmod5$$ so my answer was $$1$$ since it is in $${0, 1, 2, 3, 4}$$.

• I believe you are correct if it's only for the numbers you've listed. That's because 7 and 5 are prime, so they will only have 1 solution for any 7/5 consecutive integers. – Jaemin Kim Oct 17 at 0:04

In these problems, you can plug in each of the possible values for $$x$$ (since there are finitely many), and see which ones work. For the first problem, it is indeed true that only $$x\equiv 6\pmod{7}$$ is a solution, and for the second, it is true that only $$x\equiv 1\pmod{5}$$ is a solution.

If you know about fields, it turns out that $$\Bbb{F}_p = \Bbb{Z}/(p)$$ (i.e., the set of numbers you use in modular arithmetic) forms a field when $$p$$ is a prime number. Given a linear equation $$ax + b = c$$ where $$a\neq 0,b,$$ and $$c$$ are elements of your field, there exists a unique solution given by $$x = (c - b)a^{-1},$$ as for any nonzero element $$a$$ in a field there is a unique element $$a^{-1}$$ such that $$a a^{-1} = a^{-1}a = 1.$$

Find all solutions to: $$4x\equiv3\pmod7$$

Given

$$4x\equiv 3\pmod 7 \iff 8x\equiv 6\pmod 7 \iff x\equiv 6\pmod 7$$

then as the least residue system modulo $$7$$ is

$$\{0,1,2,3,4,5,6\}$$

we see that $$x\equiv 6\pmod 7$$ when $$x=6$$. Therefore, the only solution is $$x\equiv 6\pmod 7$$.

Find all solutions to: $$3x+1\equiv4\pmod5$$

Given

$$3x+1\equiv4\pmod5 \iff 3x\equiv3\pmod5 \iff x\equiv 1\pmod5$$

then as the least residue system modulo $$5$$ is

$$\{0,1,2,3,4\}$$

we see that $$x\equiv 1\pmod 5$$ when $$x=1$$. Therefore, the only solution is $$x\equiv 1\pmod 5$$.

To see that both solutions are unique we apply the following theorem

Theorem: If $$\text{g}=\text{gcd}(a,m)=1$$, the congruence $$ax\equiv b\pmod m$$ has exactly one solution modulo $$m$$.

In the first case, $$\text{g}=\text{gcd}(4,7)=1$$ and in the second case $$\text{g}=\text{gcd}(3,5)=1$$. Therefore, both solutions are unique.

• OP already knows the solutions but asks if they are unique. The above does not shed any light on that – Bill Dubuque Oct 17 at 1:59

For the first problem you need to find the multiplicative inverse of $$4$$ modulo $$7$$ and multiply both sides by that. This is the modular arithmetic equivalent of "dividing by 4" to solve for $$x$$. Here multiplicative inverse of $$4$$ modulo $$7$$ means an integer $$a$$ such that $$4 \cdot a \equiv 1 \pmod 7$$. You can check by trial and error that $$a=2$$ works since $$4\cdot 2 = 8 \equiv 1 \pmod 7$$. Thus, \begin{align*} 4x&\equiv 3 \pmod 7\\ 2\cdot 4 x &\equiv 2 \cdot 3 \pmod 7\\ 8x &\equiv 6 \pmod 7\\ x &\equiv 6 \pmod 7. \end{align*} Since multiplicative inverses are unique modulo prime numbers, this will be the only solution in $$\{0,1,\dots,6\}$$.

For the second problem you can do something similar, but first move the $$1$$ to the other side to get $$3x \equiv 3 \pmod 5$$. From this it's clear that $$x=1$$ is a solution, but you can also find that by multiplying both sides by $$2$$ (the multiplicative inverse of $$3$$ modulo $$5$$). It's the only solution since again multiplicative inverses are unique modulo $$5$$.