Quadratic Polynomial Number Theory and Number FieldsDate: 05/12/2004 at 17:40:53 From: John Subject: Perfect squares generated by second degree polynomials I have the polynomial P(x) = 2*x^2 + 3*x + 4, and I'm trying to find all values of x for which P is a perfect square. I wrote a program that calculated the value of P(x), where 1 <= x <= 30000, and I found these perfect squares: P(1) = 9 P(36) = 2704 P(65) = 8649 P(1248) = 3118756 P(2233) = 9979281 My program can't run further, so those are the values I have to work with, and I don't see any connection between the x values. Are there infinite values of x that generate perfect squares for P? Is there a formula to generate those x values? From there, is there a general formula for P(x) = a*x^2 + b*x + c? Date: 05/12/2004 at 22:26:03 From: Doctor Vogler Subject: Re: Perfect squares generated by second degree polynomials Hi John, Thanks for writing to Dr Math. Good question! I congratulate you for writing a program to check a bunch of numbers. That's often a very good first step, because it can show you what you need to prove. For example, if you only get one, then you try to prove that there are no more. If you see a pattern in the numbers you get, you try to prove it always works. In your case, it looks like there will be more solutions, but it isn't clear what the pattern is. So you are looking for integer solutions to the equation 2*x^2 + 3*x + 4 = y^2. It so happens that there is a trick to finding all rational solutions to quadratic equations in two variables, and this will usually help you find integer solutions. The idea is to start with one known rational point, like (0, 2). Then if you have any other rational point (x, y) on the curve, those two points will form a line with rational slope. Well, no matter what line we pick which has rational slope m and goes through the point (0, 2), such as y = m*x + 2 it will always intersect the quadratic equation in two points. Solve like so: 2*x^2 + 3*x + 4 = (m*x + 2)^2 x*(2*x + 3) = x*(m^2*x + 4*m) so x = 0 (and y = 2), or 2*x + 3 = m^2*x + 4*m x = (4*m - 3)/(2 - m^2) y = (2*m^2 - 3*m + 4)/(2 - m^2). Now if we write the rational number m as a/b (where a and b are integers), then we find that our solutions are x = (4*a*b - 3*b^2)/(2*b^2 - a^2) y = (2*a^2 - 3*a*b + 4*b^2)/(2*b^2 - a^2). So the question now is: When does 2*b^2 - a^2 divide each of those numerators? Well, it certainly happens when 2*b^2 - a^2 is 1 or -1, and a little bit of algebraic number theory will tell you when that happens. I won't go into the number theory, but it is exactly when a + b*sqrt(2) = (1 + sqrt(2))^k for some integer k. The easiest way to deal with this is as a recurrence relation. Start with a = b = 1 (k = 1). (This gives x = 1, y = 3, which was your first solution.) Then change the pair (a, b) into (a + 2b, a + b), and repeat (each step increases k by 1). So this gives: a = 1 b = 1 x = 1 y = 3 a = 3 b = 2 x = -12 y = -16 a = 7 b = 5 x = 65 y = 93 a = 17 b = 12 x = -384 y = -542 a = 41 b = 29 x = 2233 y = 3159 ... ... ... ... And then you can also work backwords (each step will decrease k by 1). Do this by changing the pair (a, b) into (2b - a, a - b) This gives you the same thing with one of the two variables negated (if you negate both of them, you get the same x's and y's): a = 1 b = 1 x = 1 y = 3 a = 1 b = 0 x = 0 y = -2 a = -1 b = 1 x = -7 y = 9 a = 3 b = -2 x = 36 y = -52 a = -7 b = 5 x = -215 y = 303 a = 17 b = -12 x = 1248 y = -1766 ... ... ... ... Of course, I haven't proven that these are the only squares that the polynomial will produce (although I believe that is true as well), but I have accounted for all of the squares you found, and I've given you a method for generating infinitely many more. I hope you enjoyed this, and I hope you learned something! 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/ Date: 05/13/2004 at 01:11:56 From: John Subject: Perfect squares generated by second degree polynomials Thank you very much for your fast, professional, and very polite answer. It was very interesting. I do have some further questions, if possible: 1) My original problem, which generated today's question, was this. I want to write a program to find ONE solution of this equation: m ( x + y ) + n * x * y = q (where m, n, q are entered by the user) but I don't want to use factorization, for a lot of reasons. All solutions I found to this Diophantine (is this the right term?) equation required factorization. 2) Do you know of any online books I can read about the number theory you referred to? I can't afford investing in books or other publications. 3) How do I find a rational solution for P(x) = a*x^2 + b*x + c, when c is not a perfect square (I used 4 in my original example)? Thank you very much, John Date: 05/13/2004 at 09:56:42 From: Doctor Vogler Subject: Re: Perfect squares generated by second degree polynomials Hi John, I'm glad you are following this and asking more good questions. In the order that you asked: 1) Do you mean integer factorization, or polynomial factorization? I would solve your equation like this: mx + my + nxy = q x(m + ny) = q - my q - my x = -------- m + ny m qn + m^2 x = - --- + ---------- n n(m + ny) and then probably factor out a GCD of the fraction on the right in order to make the numbers smaller. You can also write this as: (m + nx)(m + ny) = qn + m^2, which is easy to see to be equivalent to your original equation (unless n = 0, but then you just have x + y = q/m). Then you can take the number on the right, qn + m^2, and factor it. I know you said you didn't want to factor, but the only other option that I see is trying lots of values for x and y until you find a solution, and that's slower than integer factorization. Anyway, you get the prime factorization of qn + m^2, use that to get a list of all of the factors (and you should include the negatives as well). Then for each factor f, you see if x = (f - m)/n is an integer, and if y = ([qn + m^2]/f - m)/n is an integer. If you think about this, you'll find that it also constitutes a proof that these will give you *all* integer solutions. You can also make your job easier by first taking the GCD of m and n (call it g), and factoring g^2 out of the product on the left. Now, if g^2 does not divide the expression on the right, then there are no integer solutions. If it does, then divide both sides, and now you have a smaller number to factor. 2) I'm not an expert on online books. But you can search the internet for "number theory" and "number fields" and "Dirichlet unit theorem." When I did the latter, I found a series of pdf files at: http://www.math.uiuc.edu/~r-ash/Ant/AntChapter1.pdf http://www.math.uiuc.edu/~r-ash/Ant/AntChapter2.pdf http://www.math.uiuc.edu/~r-ash/Ant/AntChapter3.pdf http://www.math.uiuc.edu/~r-ash/Ant/AntChapter4.pdf http://www.math.uiuc.edu/~r-ash/Ant/AntChapter5.pdf http://www.math.uiuc.edu/~r-ash/Ant/AntChapter6.pdf http://www.math.uiuc.edu/~r-ash/Ant/AntChapter7.pdf http://www.math.uiuc.edu/~r-ash/Ant/AntChapter8.pdf http://www.math.uiuc.edu/~r-ash/Ant/AntChapter9.pdf But I personally am a fan of books and libraries. If you have access to a university library, that will definitely be your best resource. Look for a book on number fields. If not, you can try a public library as well, although they don't generally have as many math books. 3) Well, a computer search is one good way. Sometimes there are no rational solutions, and then you have something completely different to try to prove. (Modular arithmetic sometimes works to prove that there are no integer solutions, and p-adic arithmetic sometimes works to prove that there are no rational solutions. But it depends on the numbers involved.) - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/