Solving ax^2 + by + c = 0 Using Modular Arithmetic

Date: 10/09/2004 at 04:42:29
From: Meriam
Subject: Diophantine equation

I would like to know the sufficient and necessary conditions so that
ax^2 + by + c = 0 is solvable, where x and y are to be determined.  In
general, if p is an odd prime, when will x^2 + py + c = 0 be solvable?

Can I use the principles of quadratic equations?

I have visited Dario Alejandro Alpern's page at 

    http://www.alpertron.com.ar/METHODS.HTM 

but there is no particular form or case that fits to this problem.

Date: 10/19/2004 at 11:09:32
From: Doctor Vogler
Subject: Re: Diophantine equation

Hi Meriam,

Thanks for writing to Dr Math.

If you were happy with rational solutions, then you could pick any
rational x and solve for y

  y = -(ax^2 + c)/b.

Of course, you probably already knew that, and you wanted integer
solutions.  Well, you can still solve for y, which means that the only
thing you really need to do is determine when

  ax^2 + c

is divisible by b.  This is a question for modular arithmetic.  Are
you familiar with modular arithmetic?  You can learn a little bit from
our archive, such as

  Mod, Modulus, Modular Arithmetic
    http://mathforum.org/library/drmath/view/62930.html 

Your problem is to decide whether

  x^2 = -c/a (mod b)

has any solutions.  First of all, to divide by a, the numbers a and b
have to be relatively prime.  If a and b have a common factor, then c
had better also have the same factor, or else there will be no
solutions.  (Can you explain why?  Look at the original equation.)  If
all three have the same common factor, then you can divide the whole
equation by that common factor.

So now we can assume that a and b are relatively prime, which means
that a has a multiplicative inverse mod b (a number x such that ax-1
is divisible by b; you can find this number x using the Euclidean
Algorithm).  Multiply by -c, and now you need to know if that number
is a square mod b.

That last problem is called deciding if -c/b is a "quadratic residue"
mod b.  (Meaning a square mod b.)  If b is small, then you just check
the squares of all of the numbers from 0 to b-1 (square them, and see
if one of them is -c/a mod b).  If b is big, this will take a LONG
time.  Well, there is a really neat technique called "quadratic
reciprocity" that can answer the same question very quickly, even for
big b.

You can learn about quadratic reciprocity and the Euclidean algorithm
by searching our archives, or MathWorld,

    http://mathworld.wolfram.com/ 

or the internet.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/