Find all the solutions of the congruence

[Math100]

Homework Statement

Find all the solutions of the congruence $7x^2+15x\equiv 4\pmod {111}$.

Relevant Equations

None.

Consider the congruence $7x^2+15x\equiv 4\pmod {111}$.
Note that $4\cdot 7=28$.
Then $7x^2+15x\equiv 4\pmod {111}\implies 196x^2+420x-112\equiv 0\pmod {111}$.
Observe that
\begin{align*}
&196x^2+420x-112\equiv 0\pmod {111}\\
&\implies (14x)^2+2(14x)(15)+15^2-112-225\equiv 0\pmod {111}\\
&\implies (14x+15)^2\equiv 337\pmod {111}\\
&\implies (14x+15)^2\equiv 4\pmod {111}\\
&\implies (14x+15)^2\equiv 2^{2}\pmod {111}\\
&\implies 14x+15\equiv \pm2\pmod {111}.\\
\end{align*}
Now we consider two cases.
Case #1: Let $14x+15\equiv 2\pmod {111}$.
Then $14x\equiv -13\pmod {111}$.
Thus $14x\equiv 98\pmod {111}\implies x\equiv 7\pmod {111}$.
Case #2: Let $14x+15\equiv -2\pmod {111}$.
Then $14x\equiv -17\pmod {111}\implies 14x\equiv 94\pmod {111}\implies 7x\equiv 47\pmod {111}$.
Thus $7x\equiv 602\pmod {111}\implies x\equiv 86\pmod {111}$.
Therefore, the solutions of the congruence $7x^2+15x\equiv 4\pmod {111}$ are $x\equiv 7\pmod {111}$ and $x\equiv 86\pmod {111}$.

 

[fresh_42]

Homework Statement:: Find all the solutions of the congruence $7x^2+15x\equiv 4\pmod {111}$.
Relevant Equations:: None.

Consider the congruence $7x^2+15x\equiv 4\pmod {111}$.
Note that $4\cdot 7=28$.
Then $7x^2+15x\equiv 4\pmod {111}\implies 196x^2+420x-112\equiv 0\pmod {111}$.
Observe that
\begin{align*}
&196x^2+420x-112\equiv 0\pmod {111}\\
&\implies (14x)^2+2(14x)(15)+15^2-112-225\equiv 0\pmod {111}\\
&\implies (14x+15)^2\equiv 337\pmod {111}\\
&\implies (14x+15)^2\equiv 4\pmod {111}\\
&\implies (14x+15)^2\equiv 2^{2}\pmod {111}\\
&\implies 14x+15\equiv \pm2\pmod {111}.\\
\end{align*}
Now we consider two cases.
Case #1: Let $14x+15\equiv 2\pmod {111}$.
Then $14x\equiv -13\pmod {111}$.
Thus $14x\equiv 98\pmod {111}\implies x\equiv 7\pmod {111}$.
Case #2: Let $14x+15\equiv -2\pmod {111}$.
Then $14x\equiv -17\pmod {111}\implies 14x\equiv 94\pmod {111}\implies 7x\equiv 47\pmod {111}$.
Thus $7x\equiv 602\pmod {111}\implies x\equiv 86\pmod {111}$.
Therefore, the solutions of the congruence $7x^2+15x\equiv 4\pmod {111}$ are $x\equiv 7\pmod {111}$ and $x\equiv 86\pmod {111}$.

Correct. However, you divided by $2,7$ and $14$ so it would be good to say that you are allowed to do this and why.

 

[Math100]

Correct. However, you divided by $2,7$ and $14$ so it would be good to say that you are allowed to do this and why.

How should I explain those divisions of $2, 7, 14$?

 

[fresh_42]

Since $111$ isn't a prime, $\mathbb{Z}_{111}$ has zero divisors. $111=3\cdot 37$ so we cannot divide by $3$ or $37$. But $2,7$ and $14$ are all coprime to $111$ so they have inverses by Bézout's lemma.

Whenever we divide, say by $14$ then what we actually do is multiply by $14^{-1}$ because the division isn't defined, only multiplication. In order to perform that multiplication, $14^{-1}$ has to exist. $37^{-1}$ does not exist modulo $111$.

 

[Math100]

Since $111$ isn't a prime, $\mathbb{Z}_{111}$ has zero divisors. $111=3\cdot 37$ so we cannot divide by $3$ or $37$. But $2,7$ and $14$ are all coprime to $111$ so they have inverses by Bézout's lemma.

Whenever we divide, say by $14$ then what we actually do is multiply by $14^{-1}$ because the division isn't defined, only multiplication. In order to perform that multiplication, $14^{-1}$ has to exist. $37^{-1}$ does not exist modulo $111$.

By Bezout's lemma, do you mean $ax+by=d$ where $a, b$ are integers with the greatest common divisor $d$?

 

[fresh_42]

By Bezout's lemma, do you mean $ax+by=d$ where $a, b$ are integers with the greatest common divisor $d$?

Yes. And in case $d=1=\operatorname{gcd}(14,111)$ we have $14\cdot a +111\cdot b=1.$ This means that $14\cdot a\equiv 1\pmod{111}$ and so $14^{-1}=a.$

 

[fresh_42]

That $37^{-1}$ does not exist modulo $111$ is similar. Assume it would exist, then
$$
3\equiv 3\cdot 1\equiv 3\cdot (37\cdot 37^{-1})\equiv (3\cdot 37)\cdot 37^{-1}\equiv 111\cdot 37^{-1}= 0 \pmod{111}
$$
which is a contradiction. Hence $37^{-1}$ cannot exist.