How do you find all the solutions of the congruence

7x^2-41x+48=0(mod333)

Printable View

- Jul 26th 2009, 10:34 PMCairoPolynomial Congruences
How do you find all the solutions of the congruence

7x^2-41x+48=0(mod333) - Jul 27th 2009, 04:50 AMTheAbstractionist
Multiplying the congruence by 28 gives $\displaystyle 196x^2-1148x+1344\equiv0\,(\bmod{}\,333).$

Note that $\displaystyle \gcd(28,333)=1$ and so the second congruence implies the first as well: i.e. $\displaystyle 7x^2-41x+48\equiv0\,(\bmod{}\,333)\ \iff\ 196x^2-1148x+1344\equiv0\,(\bmod{}\,333).$

The reason for multiplying by 28 is to make the leading coefficient a perfect square and the coefficient of $\displaystyle x$ even so that we can complete the square. Completing the square gives $\displaystyle (14x-41)^2-337\equiv0\,(\bmod{}\,333).$ Hence, letting $\displaystyle y=14x-41,$ we have to solve the congruence

$\displaystyle y^2\equiv337\,(\bmod{}\,333)\equiv4\,(\bmod{}\,333 )\quad\ldots\,\boxed1$

Clearly $\displaystyle y=2$ is a solution, so one solution to the original congruence is found by solving $\displaystyle 14x-41\equiv2\,(\bmod{}\,333)$ for $\displaystyle x.$ I can tell you that one possiblity is $\displaystyle x=122$ and substituting into the original congruence shows that $\displaystyle x=122$ is indeed one solution.

Another solution to $\displaystyle \boxed1$ is $\displaystyle y=-2.$ Find all solutions to $\displaystyle \boxed1$ and for each check and see if the corresponding solution for $\displaystyle x$ satisfies the original congruence. Good luck. (Wink)