3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jaemin Kim Oct 17 at 0:04
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

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

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

$\endgroup$

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.