3
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ what has been tried ? $\endgroup$ – user451844 Jul 12 '17 at 12:11
8
$\begingroup$

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?

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ But $x\equiv -5 (mod 11)$ is not correct@Bernard $\endgroup$ – Atul Mishra Jul 12 '17 at 12:21
  • $\begingroup$ @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! $\endgroup$ – Bernard Jul 12 '17 at 12:24
2
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ – lioness99a Jul 12 '17 at 12:16
1
$\begingroup$

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

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

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.