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!
$\begingroup$
$\endgroup$
1
asked Jul 12, 2017 at 12:07
-
$\begingroup$ what has been tried ? $\endgroup$– user451844Jul 12, 2017 at 12:11
Add a comment
|
7 Answers
$\begingroup$
$\endgroup$
1
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?
answered Jul 12, 2017 at 12:16
-
$\begingroup$ It would help those learning if you explain why you multiplied by $4$ and why/how you chose the factor $4$. $\endgroup$ Jul 12, 2017 at 14:02
$\begingroup$
$\endgroup$
${\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.
answered Jul 12, 2017 at 13:48
$\begingroup$
$\endgroup$
2
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.$$
-
$\begingroup$ But $x\equiv -5 (mod 11)$ is not correct@Bernard $\endgroup$ Jul 12, 2017 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$– BernardJul 12, 2017 at 12:24
$\begingroup$
$\endgroup$
0
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$.
$\begingroup$
$\endgroup$
$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}$.
answered Jul 16, 2017 at 16:50
$\begingroup$
$\endgroup$
1
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$
-
$\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$ Jul 12, 2017 at 12:16
$\begingroup$
$\endgroup$
3
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
answered Jul 12, 2017 at 12:14
-
$\begingroup$ Type 3x + 7 \equiv 0 \pmod{11} in math mode to obtain $3x + 7 \equiv 0 \pmod{11}$. $\endgroup$ Jul 13, 2017 at 10:13
-
$\begingroup$ So you found a particular solution($x_0$) and used $x\equiv x_0 \pmod {11}$? $\endgroup$ Jul 13, 2017 at 16:39
-
$\begingroup$ Yes you are getting me @VidyanshuMishra $\endgroup$ Jul 14, 2017 at 9:59