Quadratic residues short proof

69 Views Asked by At

I'm not too sure how to answer this question here, so if someone could help me out, that'd be great.

Super $m$ is odd and $a$ and $m$ are coprime. Show that

$ax^{2} + bx + c \equiv 0 $(mod $m)$

has an integer solution $x \equiv r ($mod $m)$ if and only if $b^{2} - 4ac$ is a square modulo $m$.

Thanks.

Edit: Here is my proposed solution based on the comments:

$ax^{2} + bx + c \equiv 0 ($mod $m) \implies x^{2} + \frac{b}{a}x + \frac{c}{a} \equiv 0 ($mod $m)$.

$\implies (x + \frac{b}{2a})^{2} - \frac{b^{2}}{4a} + \frac{c}{a} \equiv 0 ($mod $m)$.

$\implies (x + \frac{b}{2a})^{2} \equiv \frac{b^{2}-4ac}{4a^{2}} ($mod $m)$

$4a^{2}$ is always a perfect square mod $m$, so $b^{2} - 4ac$ must be a perfect square modulo $m$.

One more question is, are we allowing rational solutions for $x$? Do we have to worry about $a/c$ not being an integer, or $b^2-4ac$ being divisible by $4a^2$?

1

There are 1 best solutions below

2
On

It's possible to use rational numbers in modular arithmetic, but you have to be careful about what you mean. Instead of what you did, multiply both sides by $4a$ and put the $c$ on the other side. Then when you complete the square, you won't have fractions.