Quadratic Diophantine Equation

Date: 01/16/2009 at 11:07:02
From: Dave
Subject: Quadratic polynomial equals square of odd integer

In solving a probability and combinatorics problem, I encountered the
following question:

Find all positive integers N such that 2*N^2 - 2*N + 1 is the square
of an odd integer. 

I have found all solutions under 10 million (4, 21, 120, 697, 4060,
23661, 137904, 803761, 4684660) using the computer and could program
it to find more by looping through, but is there a general form for
the solution?  Are there finitely many solutions or infinitely many?

Thanks Dr. Math!

Date: 01/17/2009 at 04:32:22
From: Doctor Jacques
Subject: Re: Quadratic polynomial equals square of odd integer

Hi Dave,

This is a particular case of a quadratic Diophantine equation. There 
are a few articles on that subject in our archive, for example:

   Sum of First N Positive Integers Making a Perfect Square
     http://mathforum.org/library/drmath/view/70344.html 

In this case, we want to solve the equation:

  2*N^2 - 2*N + 1 = y^2   [1]

in integers (there is not need to specify that y must be odd; this 
results directly from the equation).

The first thing to do is to "complete the square", to get rid of 
linear terms. In this case, we first multiply everything by 2 to get 
a square as the leading coefficient:

  4*N^2 - 4*N + 2 = 2*y^2

and we complete the square:

  (2*N-1)^2 + 1 = 2*y^2

by putting x = 2*N-1, we can rewrite this as:

  x^2 - 2*y^2 = -1         [2]

This equation has one obvious solution: x = y = 1, corresponding to 
N = 1 (which you forgot...).

The problem is now to find all the solutions. Notice that we may 
write:

  x^2 - 2*y^2 = (x + y*sqrt(2))(x - y*sqrt(2))

and this leads us to investigate the properties of numbers of the 
form (x + y*sqrt(2)), where x and y are integers (or rationals).  
Note that those numbers constitute a ring, i.e., the sum and product 
of two such numbers is a number of the same type.

We define the conjugate of the number u = (x + y*sqrt(2)) as
u' = (x - y*sqrt(2)). This is somewhat similar to the notion of 
complex conjugates, and this is no coincidence: taking the conjugate 
amounts to replacing sqrt(2) by -sqrt(2), much like taking the 
complex conjugate amounts to replacing i by -i.

Conjugation is compatible with addition and multiplication; 
specifically, we have:

  (u + v)' = u' + v'
  (u*v)' = u' * v'                [3]

as you can easily check.

We next define the norm of the number u = x + y*sqrt(2) as the 
product of the conjugates:

  N(u) = u*u' = x^2 - 2*y^2        [4]

Because of [3], we have:

  N(u*v) = (u*v)*(u*v)'
         = u * v * u' * v'
         = (u*u')*(v*v')
         = N(u)*N(v)               [5]

Let us now return to the problem at hand. We may write the equation 
[2] as:

  N(u) = N(x*y*sqrt(2)) = -1        [6]

and we already have a solution u_1 = 1 + sqrt(2), corresponding to
x = y = 1. Because of [5], if we can find a number v = a+b*sqrt(2) 
such that N(v) = a^2 - 2*b^2 = +1, we will have:

  N(u*v) = N(u)*N(v) = (-1)*(+1) = -1

which means that u*v will be another solution of [6], from which we 
can extract the new values of x and y as the rational and irrational 
parts of (u*v), respectively. By repeating the process, we can get 
an infinity of solutions.

To find v, we need to solve:

  N(v) = a^2 - 2*b^2 = 1             [7]

for integer a and b. This is (mistakenly) known as Pell's equation. 
There is a general method, based on continued fractions, for solving 
that kind of equation, but, in this case we find easily the 
solution v = 3*2*sqrt(2) by trial and error (a more enlightened 
approach would be to notice that, as N(u) = -1, N(u^2) = +1 by [5], 
and we have v = u^2).

So, given a solution u[k] = x[k] + y[k]*sqrt(2), we find the next 
solution as:

  u[k+1] = u[k] * v
         = (x[k]+y[k]*sqrt(2))(3+2*sqrt(2))
         = (3*x[k]+4*y[k]) + (2*x[k]+3*y[k])*sqrt(2)
         = x[k+1] + y[k+1]*sqrt(2)

and this gives the recurrence relations:

  x[k+1] = 3*x[k] + 4*y[k]
  y[k+1] = 2*x[k] + 3*y[k]         [8]

As we have N = (x+1)/2, and N must be an integer, we only need the 
solutions with x odd, but, as [8] shows, if x[1] is odd (and this is 
the case), all subsequent values of x will also be odd.

Starting with x[1] = y[1] = 1, we find the first few solutions:

     x    y    N
  ---------------
     1    1     1
     7    5     4
    41   29    21
   239  169   120
  1393  985   697

We may also find an explicit form for the general solution. Note 
that, if u = (x+y*sqrt(2)), we have:

  x = (u + u')/2
  y = (u - u')/(2*sqrt(2))

and, as we have:

  u[k] = u[1]*v^k
       = [1+sqrt(2)) * (3+2*sqrt(2)]^k

we get:

  x[k] = [(1+sqrt(2))*(3+2*sqrt(2))^k +
               (1-sqrt(2))*(3-2*sqrt(2))^k]/2

In this particular case, as noted before, we have v = u[1]^2, and we 
may simplify the above expression as:

  x[k] = [(1+sqrt(2))^(2k+1) + (1-sqrt(2))^(2k+1)]/2

There is a whole theory about the solution of this type of 
equations, the theory of quadratic forms, developed by Gauss; this 
is only a very simple case.

Please feel free to write back if you require further assistance.


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

Date: 01/18/2009 at 12:49:01
From: Dave
Subject: Quadratic polynomial equals square of odd integer

Thanks for the help!  The problem was this:

A drawer contains N socks, of which r are red and the rest are black.
The probability of drawing 2 red socks is exactly 1/2.  How many socks
are there?  And how many are red?

r and N must be positive integers (r is at least 2) and must satisfy
the equation 2*r*(r-1) = N*(N-1). 

I followed your method and found solutions for r and N in terms of odd
powers of 1+sqrt(2).  (Take x = 2*N-1, y = 2*r-1, u = x+y*sqrt(2),
then N(u) = -1, etc.)

To finish this off, is there any way to show that any solution of the
equation N(u) = -1 must be of this form, without appealing to abstract
algebra (rings, units, etc)?  This is for a probability class in which
most students have not taken abstract algebra.  I searched through the
resources on here and the links to external websites, but none of them
have an answer to this one.

Thanks again!

Date: 01/19/2009 at 02:58:30
From: Doctor Jacques
Subject: Re: Quadratic polynomial equals square of odd integer

Hi Dave,

Unfortunately, I don't believe that this can be proved in an 
elementary way.  The main issue is to prove that all integer 
solutions of the equation x^2 - 2*y^2 = (+/-)1 come from powers of a 
single number, called a fundamental unit (in this case, 1+sqrt(2)). 
This is called Dirichlet's Unit theorem, and it requires some 
knowledge of algebraic number theory.


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

Date: 01/19/2009 at 06:41:58
From: Dave
Subject: Thank you (Quadratic polynomial equals square of odd integer)

Thanks for all your help with this problem!