1
$\begingroup$

I found a systematic way (c.f. How to solve this quadratic congruence equation) to solve all congruent equations of the form of $ax^2+bx+c=0\pmod{p}$, or to determine that they have no solution.

But I wonder if there is some easy way to find solutions of simple quadratic congruent equations by inspection, for example, for this equation $$x^2+x+47=0\pmod{7}.$$

My textbook gave the solutions $x\equiv 5\pmod{7}$ and $x\equiv 1\pmod{7}$ directly, without any proof. So I think there must be some easier way to inspect the solutions.

Any help will be appreciated.

$\endgroup$
  • 2
    $\begingroup$ Note: $x^2+x+47\equiv x^2-6x+5\pmod 7$ $\endgroup$ – J. W. Tanner May 10 at 14:23
  • $\begingroup$ Also you can note that $x(x+1)=-5=2$ $\endgroup$ – Piquito May 10 at 14:35
  • $\begingroup$ @J.W.Tanner What an excellent observation! Thanks Tanner. $\endgroup$ – Sam Wong May 10 at 20:54
  • $\begingroup$ @Piquito Thanks for your observation too. But I think Tanner's observation is more straightforward :) $\endgroup$ – Sam Wong May 10 at 20:55
2
$\begingroup$

The good old quadratic equation works just fine if $p\neq2$. If $a\not\equiv 0\pmod{p}$ and $b^2-4ac$ is a quadratic residue mod $p$, then the solutions to the quadratic congruence $$ax^2+bx+c\equiv0\pmod{p},$$ are precisely $$-\frac{b\pm\sqrt{b^2-4ac}}{2a}.$$

In this particular case we have $p=7$ and $a\equiv b\equiv1\pmod{7}$ and $c\equiv47\equiv5\pmod{7}$. Then $$b^2-4ac\equiv2\equiv3^2\pmod{7},$$ so the congruence has the two solutions $$-\frac{1+3}{2}=5\qquad\text{ and }\qquad-\frac{1-3}{2}=1.$$


On the other hand, if you want to solve it purely by inspection, note that there are only $7$ possible solutions to check. Clearly $x=0$ is not a solution, and plugging in $x=1$ yields the first solution. The product of the solutions is congruent to $47\equiv5\pmod{7}$, so the other solution is $x=5$.

$\endgroup$
  • $\begingroup$ Thanks Servaes. But I still have problems in understanding your last sentence. Why is that the product of the solutions is congruent to $47\equiv 5\, ($mod$ \, 7)$ ? And why if it is so, the other solution will be $x=5$? Thanks for your elaboration. $\endgroup$ – Sam Wong May 10 at 20:54
  • 2
    $\begingroup$ @SamWong: the product of the roots of $x^2+bx+c=0$ is $c$, so $5$ in this case, and the solution of $1\times x\equiv5$ is $x\equiv5$ $\endgroup$ – J. W. Tanner May 10 at 21:10
  • $\begingroup$ @J.W.Tanner Oh I see. Thanks! $\endgroup$ – Sam Wong May 10 at 22:41
2
$\begingroup$

Servaes gave a good general method for solving quadratic equations modulo a prime.

I will elaborate on my comment about how in this particular case the answer could be found by inspection.

Adding or subtracting a multiple of $p$ to or from any of the coefficients $a,b,c$

does not materially change the equation $ax^2+bx+c\equiv0\mod p.$

In fact, $x^2+x+47$ begs to be reduced modulo $7$ to $x^2+x+5.$

$x^2+x+5$ doesn't have rational roots, but you could add or subtract any multiple of $p$ to the $x$-coefficient $1$,

yielding polynomials such as $x^2+8x+5, x^2-6x+5,$ etc.,

and $x^2-6x+5$ is easily recognized as $(x-1)(x-5)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.