# Find all $x$ such that $11\mid 3x+7$

I found this question in Beachy and Blair: Abstract algebra book, they even have a solution to this but its not satisfactory for me. They only say "$x\equiv 5 \pmod{11}$ ". Which one can "feel" simply by trial and error. I would like to know what is the proper approach. Thank you in advance!

• what has been tried ? – user451844 Jul 12 '17 at 12:11

## 7 Answers

We need $3x+7\equiv 0\pmod{11}$

Add 4 to both sides:

$$3x+11\equiv 4\pmod{11}$$

reduce:

$$3x \equiv 4\pmod{11}$$

multiply both sides by a number to make the coefficient on the left equivalent to $1$. In this case, $4$ works:

$$12x\equiv 16\pmod{11}$$

reduce:

$$x\equiv 5\pmod{11}$$

Does that work for you?

• It would help those learning if you explain why you multiplied by $4$ and why/how you chose the factor $4$. – Bill Dubuque Jul 12 '17 at 14:02

${\rm mod}\ 11\!:\,\ 3x\equiv -7\equiv 4\iff x\equiv \overbrace{\dfrac{\color{#c00}4}3\equiv \dfrac{\color{#c00}{15}}3}^{\large \color{#c00}{4\ \equiv\ 15}}\equiv 5$

Remark  More generally we can use the extended Euclidean algorithm (esp. simple in fractional form) to invert $3$ modulo $11$. But for small numbers other methods are often simpler, e.g. adding $\pm\rm modulus$ to make the division exact (e.g. above we added $11$ to $\color{#c00}4$ to make it divisible by $3)$

Beware $\$ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

It's simpler to use congruences: $11\mid 3x+7$ means $3x+7\equiv 0 \mod11$, or $$3x\equiv -7\equiv 4\mod4,$$ so all we have to do is finding the inverse of $3$ mod. $11$.

This comes with a Bézout's relation obetween $3$ and $11$: $4\cdot 3-11=1$, thus $4\cdot 3\equiv 1\mod 11$, therefore $$4\cdot 3x\equiv 4^2\iff x\equiv 5\mod11.$$

• But $x\equiv -5 (mod 11)$ is not correct@Bernard – Atul Mishra Jul 12 '17 at 12:21
• @Atul Mishra: I've seen that and already fixed it (I had swapped $-7$ and $4$ in the first display equation). Thanks for pointing it! – Bernard Jul 12 '17 at 12:24

We need to find all integers $x$ such that

$3x = 11y - 7$ for some integers $y$

$3x = 11(y-2) -7 + 22 = 11(y-2) + 15$ and we get $3x - 15 = 11(y-2)$.

So $11 \mid (3x - 15)$ which can be written $11 \mid 3(x-5)$. $\gcd(3,11) = 1$ and by Euclid's Lemma $11 \mid (x-5)$ then $x = 11t+5$ ($t$ integer) are all the integers such that $3x+7$ is divisible by $11$.

$11\mid 3x+7$ is the same thing as saying there exists an integer $y$ such that $3x + 7 = 11y$.

Trying $y=0, 1$ and finally $y=2$, we find that $x=5$ and $y=2$ is a solution. So we consider solutions of the form $x = 5+u$ and $y=2+v$.

\begin{align} 3x + 7 &= 11y \\ 3(5+u) + 7 &= 11(2+v) \\ 15 + 3u + 7 &= 22 + 11v \\ 3u + 22 &= 11v + 22 \\ 3u &= 11v \\ 3 &\mid 11v \\ 3 &\mid v \end{align}

So $v = 3t$ and $y=2+3t$ for some integer $t$. The "for some" part is a problem. It suggests that, sometimes, $y=2+3t$ may not be a solution. It is very easy to show $y=2+3t$ is always going to be a solution.

Start with $3x+7=11y$ and let $y = 2+3t$.

\begin{align} 3x+7 &= 11y \\ 3x + 7 &= 11(2+3t) \\ 3x + 7 &= 22 + 33t \\ 3x &= 33t + 15 \\ x &= 11t + 5 \end{align}

But, of course, saying $x = 11t+5$ for any integer $t$ means that $x \equiv 5 \pmod{11}$.

We need $$3x+7=11y\iff11y-3x=7(12-11)\iff11(y+7)=3(x+28)$$

$\implies\dfrac{3(x+28)}{11}=y+7$ which is an integer

$\iff11|3(x+28)\iff11|(x+28)$ as $(3,11)=1$

$\implies x\equiv-28\pmod{11}\equiv-28+33$

• It might be worth adding a few lines to explain some of the steps, I am struggling to follow everything you've written. Some justification for some of the steps would be nice – lioness99a Jul 12 '17 at 12:16

According to you $$3x+7\equiv 0 \pmod{11}$$ $$3x\equiv -7\pmod{11}$$ $$3x\equiv 4\pmod{11}$$ $$3x+11y=4$$ Note that $$3(4)+11(-1)=1$$ which can be deduced by Bezout's identity

Multiplying throughout by $4$ $$3(16)+11(-4)=4$$ which gives $$x=16$$ $$x\equiv 16\pmod{11}$$ $$x\equiv 5\pmod{11}$$

Not so impressive solution but an easier approach to solve this

• Type 3x + 7 \equiv 0 \pmod{11} in math mode to obtain $3x + 7 \equiv 0 \pmod{11}$. – N. F. Taussig Jul 13 '17 at 10:13
• So you found a particular solution($x_0$) and used $x\equiv x_0 \pmod {11}$? – Vidyanshu Mishra Jul 13 '17 at 16:39
• Yes you are getting me @VidyanshuMishra – Atul Mishra Jul 14 '17 at 9:59