# Find all the solutions of the congruence

• Math100

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

Math100 said:
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.

fresh_42 said:
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 ##?

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
fresh_42 said:
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 ##?

Math100 said:
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.##

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

Math100