Associated Topics || Dr. Math Home || Search Dr. Math

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

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!
Associated Topics:
College Modern Algebra
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search