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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.