Find all the solutions of the congruence

  • Thread starter Math100
  • Start date
In summary, a congruence is a mathematical concept that compares two numbers or quantities in terms of their remainders when divided by a third number, called the modulus. To find all the solutions of a congruence, one can use the Chinese Remainder Theorem (CRT) or the Extended Euclidean Algorithm. A congruence can have multiple solutions, with the number of solutions equal to the product of the moduli when using CRT. However, when using the Extended Euclidean Algorithm, there will only be one unique solution. The main difference between a congruence and an equation is that an equation has one unique solution, while a congruence can have multiple solutions. A congruence can also have no solutions, which
  • #1
Math100
802
221
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} ##.
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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 ##?
 
  • #4
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##.
 
  • Like
Likes Math100
  • #5
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 ##?
 
  • #6
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.##
 
  • Like
Likes Math100
  • #7
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.
 
  • Like
Likes Math100

FAQ: Find all the solutions of the congruence

What is a congruence?

A congruence is a mathematical concept that describes the relationship between two numbers or objects that have the same remainder when divided by a given number.

What is the purpose of finding all solutions of a congruence?

Finding all solutions of a congruence allows us to determine all possible values of a variable that satisfy the congruence, which can be useful in solving equations and proving theorems in number theory.

How do you find all solutions of a congruence?

To find all solutions of a congruence, we use modular arithmetic and a systematic approach to test different values of the variable until we find all possible solutions that satisfy the congruence.

Can there be more than one solution to a congruence?

Yes, there can be multiple solutions to a congruence. In fact, there can be an infinite number of solutions depending on the given congruence and the range of values for the variable.

What is the difference between a congruence and an equation?

A congruence involves finding solutions that satisfy the given relationship between two numbers, while an equation involves finding a specific value for a variable that makes the equation true. Additionally, congruences use modular arithmetic, while equations use standard arithmetic operations.

Back
Top