1
$\begingroup$

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$?

$\endgroup$
9
  • 1
    $\begingroup$ Just mimic the proof of the quadratic formula. $\endgroup$
    – Mummy the turkey
    Oct 6, 2020 at 13:22
  • $\begingroup$ What happens if you attempt to complete the square? Are there any other usual quadratic equation approaches you are aware of that may help here? $\endgroup$
    – abiessu
    Oct 6, 2020 at 13:22
  • 1
    $\begingroup$ Start by saying $ax^2+bx+c\equiv0$ and, as suggested above, mimic the proof of the quadratic formula, but for integers mod $m$ rather than for real numbers $\endgroup$
    – J. W. Tanner
    Oct 6, 2020 at 13:32
  • 1
    $\begingroup$ @Cjw123 you need to be more careful in what you say. In particular $1/a$ is not a thing in this context. You must note that since $gcd(a, m) = 1$ $a$ has a multiplicative inverse mod $m$. In this way it is better to write "$a^{-1}$" to mean the "inverse of $a$ in the ring $\mathbb{Z}/m\mathbb{Z}$." This way we are not "allowing rational solutions" - we are just never leaving $\mathbb{Z}/m\mathbb{Z}$. You should also notice that you have only shown one direction (although the other should not be hard from where you are) $\endgroup$
    – Mummy the turkey
    Oct 6, 2020 at 17:52
  • 1
    $\begingroup$ Similarly when you "divide by 2" this is admissable since $m$ is odd, so $2$ has a multiplicative inverse mod $m$. These are all things you should be noting in your proof $\endgroup$
    – Mummy the turkey
    Oct 6, 2020 at 17:53

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Perhaps I'm making a really dumb algebra error, but I'm getting the following: $ax^2 + bx + c \equiv 0 (modm) \implies 4a^2x^2 + 4abx \equiv -4ac (modm).$ When I'm completing the square on $4a^2x^2+4abx$, I'm trying to form it into 4(ax+b)^2 but i'm getting an extra factor of $abx$ on there. I'm doing something wrong.... $\endgroup$
    – user817934
    Oct 6, 2020 at 13:53
  • $\begingroup$ @Cjw123 You should form it into $(2ax +b)^2$ instead. $\endgroup$
    – player3236
    Oct 6, 2020 at 14:04

You must log in to answer this question.