Quadratic Polynomial Number Theory and Number Fields

Date: 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/