Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Solving with the Pell Equation

Date: 11/15/2004 at 23:24:09
From: Matt
Subject: Integer Solutions greater than 1000 to x^2-29y^2=7

In class we are discussing how to solve problems of the form 
x^2 - ny^2 = N for fixed (n,N).  The process is fairly simple if 
|N| < n^(1/2); however, how does one find solutions if |N| > n^(1/2)?

Specifically, how does one extract integer solutions to 
x^2 - 29*y^2 = 7 with x and y being integers greater than 1000?

I can't think of a way to do it other then just writing a program to
do it for me.  The only thing I can think of is dividing by 7 to get
an N < n^(1/2), but then that changes how the whole problem works.


Date: 11/16/2004 at 14:57:54
From: Doctor Vogler
Subject: Re: Integer Solutions greater than 1000 to x^2-29y^2=7

Hi Matt,

Thanks for writing to Dr. Math.  Your question opens a door to a field
of math that has been studied in great depth by some of the world's
best mathematicians of years gone by (and a few of more recent years).
It is more customary to use d instead of n, so I shall write your
equation as

  x^2 - d*y^2 = N.

It turns out that finding all solutions to this equation generally
requires finding all solutions to the equation

  x^2 - d*y^2 = 1,

which is known as the "Pell Equation" due to an error by Euler (he
incorrectly attributed Pell with a method of solution of this kind of
equation, and the name stuck).

MathWorld is always a nice resource, so I'll provide a link to their
page on the Pell Equation:

  Pell Equation
    http://mathworld.wolfram.com/PellEquation.html 

The history begins with Archimedes' Cattle Problem, back in ancient
Greece.  Here is the MathWorld page describing the problem.  (It's not
as colorful as some links, but it's descriptive.)

  Archimedes Cattle Problem
    http://mathworld.wolfram.com/ArchimedesCattleProblem.html 

But my favorite article on Archimedes' Cattle Problem is found on the
following page:

  Solving the Pell Equation
    http://www.ams.org/notices/200202/200202-toc.html 

This covers the history of the Pell Equation, with the Cattle Problem
being the main focus of the paper.  It discusses the mathematics
involved, but only at a level to understand the history rather than to
really understand the mathematics.  So it's a nice overview, very
interesting, and not too dense.

Then on the page

  Home Page for John Robertson
    http://hometown.aol.com/jpr2718/ 

there are several articles he wrote about solving the Pell Equation
and solving the more general form of it that you gave,

  x^2 - d*y^2 = N,

as well as solving the general second-order Diophantine equation, which is

  a*x^2 + b*xy + c*y^2 + d*x + e*y + f = 0

where a, b, c, d, e, and f are given integers, and we want all
solutions in integers for (x, y).

There are also a couple of answers from our own archives that use the
Pell Equation,

  Proof Using Pell's Equation
    http://mathforum.org/library/drmath/view/53195.html 

  Recurrence Relation for a Pell Equation
    http://mathforum.org/library/drmath/view/55938.html 

one of which gives a brief description of the continued fraction method.

You might want to stop here, because the articles I mentioned on

  Home Page for John Robertson
    http://hometown.aol.com/jpr2718/ 

use none of the theory that I am about to describe, so you don't need
to keep reading, but I think it helps understanding, so I will go on.

It seems to me that the greatest amount of understanding in solving
the equation

  x^2 - d*y^2 = N

comes from the genre of mathematics known as "number fields," and real
quadratic number fields in particular.  Those are fields (as in
abstract algebra's groups, rings, and fields) which are quadratic
extensions of the rational numbers, namely

  Q[sqrt(d)].

A real quadratic number field consists of numbers of the form

  a + b*sqrt(d)

where a and b are rational numbers.  More important are the algebraic
integers in this field, which are those elements that are roots of
monic polynomials with integer coefficients.  See also

  Algebraic Integer
    http://mathworld.wolfram.com/AlgebraicInteger.html 

It turns out that for most d (as long as d-1 is not divisible by 4),
the algebraic integers in this field are those which have integers for
a and b.  (If d-1 is divisible by 4, then the algebraic integers are
the ones for which a+b and 2a are integers, meaning that a and b can
be half integers, but they have to be half integers together.  This is
why a 4 crops up in some equations, rather curiously.  But let's
ignore this for now.)

So in this field, your equation factors as

  N = x^2 - d*y^2 = (x - y*sqrt(d))*(x + y*sqrt(d)).

So all we have to do now is factor N into algebraic integers.

The set of algebraic integers forms a ring that behaves rather like
the integers do.  It turns out that when d is positive (and not a
square) then there are infinitely many units in this ring, and they
consist of all powers of some so-called fundamental unit, times the
various roots of unity in the ring (usually just 1 and -1).  That is
the Dirichlet Unit Theorem.  That means that if we have any one solution,

  x^2 - d*y^2 = N,

then we can multiply

  x + y*sqrt(d)

by any power of the fundamental unit

  (a + b*sqrt(d))^k

and get another solution (infinitely many more solutions).  The
fundamental unit is the smallest positive solution to

  x^2 - d*y^2 = +1 or -1.

(But use +4 or -4 when d-1 is divisible by 4.)

To get all solutions, we just do the above after factoring N in the
ring of algebraic integers.  Factoring bahaves a little funny,
however, and depends quite a lot on the number d.  Without going into
too much detail, I will only say that you need to factor numbers in
ideals.  (Do you remember ideals from abstract algebra?  This is where
they came from and why they were invented.)  There is a lot of math to
learn here, so I would refer you to a text book.  I learned from the book

  Number Fields

by David A. Marcus, which I thought was very readable and quite
understandable (after you've done abstract algebra), but there are
many other books also available on the same subject.

Finally, I'll get to the punch line:

You have the equation

  x^2 - 29*y^2 = 7

so your quadratic number field is

  Q[sqrt(29)]

and your Pell Equation is

  x^2 - 29*y^2 = +4 or -4.

The smallest positive solution to this equation is

  x = 5, y = 1,

which gives the fundamental unit

  u = (5/2) + (1/2)*sqrt(29)

(It turns out that u^k has integers--not half integers--exactly when
k is a multiple of 3.  You can check this using a little modular
arithmetic and recurrence relations for getting u^(k+1) from u^k.)

Finally, we need to factor 7 in the number field.  Prime numbers
sometimes remain prime in a number field, but not always.  In this
case, it does not.  In fact,

  (7) = (6 + sqrt(29)) * (6 - sqrt(29)).

It might have happened that the factors had half-integers, in which
case we would have to deal with other powers of u.  But since they are
integers, all solutions will be

  x + y*sqrt(29) = u^(3k) * (6 + sqrt(29))

and

  x + y*sqrt(29) = u^(3k) * (6 - sqrt(29))

where k is a (positive or negative) integer.  If you pick large
numbers for k, then x and y will be very large, even bigger than 1000.

I should also point out that the "recurrence relations," that many of
the links I provided will refer to, generally get from one equation to
another by multiplying by (a power of) the fundamental unit.  So,
essentially you get from one solution to another by multiplying by

  u^3 = 70 + 13*sqrt(29).

I hope all of this was interesting and helpful.  I hope you enjoy some
of those links I included.  And I hope you learn some interesting
mathematics as you work with these Pell Equations.  I find this kind
of thing fascinating, and I hope you do too.

If you have any questions about this or need more help, please write
back, and I will try to offer more advice.

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

Date: 02/08/2016 at 20:07:33
From: Ian
Subject: Solutions greater than 1000 to x^2 - 29y^2 = 7

Doctor Vogler has posted the very informative and interesting reply to 
"integer solutions greater than 1000 to x^2 - 29y^2 = 7," as above.

After I tried this method, I discovered that the solutions only applied to 
minus 7. Can you advise what small change is needed to yield the solutions 
for plus 7?
 
This is my version of the background theory he explained:

If x = p, y = q are the smallest positive solutions to the related Pell 
equation x^2 - Dy^2 = +1 or -1, then u = p + qmod(D) is the fundamental 
unit. In the case that D - 1 is divisible by 4, obtain p and q as integer 
solutions to x^2 - Dy^2 = +4 or -4, but the fundamental unit we have to 
use in that case is u = (1/2)[p + qmod(D)].

The Dirichlet Unit Theorem states that if x = a, y = b is a basic solution 
to x^2mod(D)y^2 = N then all new integer solutions x, y may be found by 
equating either of the following for some power k of the fundamental unit:

   [a - bmod(D)] u^k = x - ymod(29)
   [a + bmod(D)] u^k = x + ymod(29)

Example: Find solutions each larger than 1000 to x^2 - 29y^2 = 7.

29mod(1) is divisible by 4. Fortunately, a simple solution to 
x^2 - 29y^2 = -4 is offered by 25mod(29) = -4 with a = 5, b = 1, so 
u = (1/2)[5 + mod(29)] is the fundamental unit for this example.

Also, conveniently, a = 6, b = 1 is a basic solution to the original 
x^2 - 29y^2 = 7.

The Dirichlet Unit Theorem promises that, for some power k, we will obtain 
either of the following for integers x and y:

   [6 - mod(29)][5/2 + mod(29)/2]^k = x - ymod(29)
   [6 + mod(29)][5/2 + mod(29)/2]^k = x + ymod(29)

We get integers (rather than half integers) when k is a multiple of 3, so 
we get from one solution to another by multiplying by u^3 = 70 + 13mod(29).

Understood so far; but when we try that out, we have

   [6 - mod(29)]u^3 =  43 +  8mod(29),  and 43^2mod(29)*8^2   = -7
   [6 + mod(29)]u^3 = 797 + 148mod(29), and  797mod(29)*148^2 = -7

This is obviously very close to finding the solution, but it gives MINUS 7.

So I understand the theory, but this approach applies only to -7, not +7.

Date: 02/09/2016 at 00:26:43
From: Doctor Vogler
Subject: Re: Solutions greater than 1000 to x^2 - 29y^2 = 7

Hi Ian,

Thanks for writing to Dr. Math. 

Wow. I guess I've been doing this for a long time. That was more than 11 
years ago.

Okay, let's check my math. So the "norm" is defined by

   Norm(x + y*sqrt(29)) = N(x + y*sqrt(29)) = x^2 - 29y^2

So Norm(6 + sqrt(29)) = 7, but Norm(5/2 + 1/2*sqrt(29)) = -1.

Since N(u) = -1, that means that we need an even power of u if we want to 
get a norm of 7. So u^{3n}*(6 + sqrt(29)) is correct, but only for even n. 
So the smallest solution is x = 6 and y = 1. 

When you multiply by u^3 = 70 + 13*sqrt(29), then you get a number 
(797 + 148*sqrt(29)) of norm -7. And if you multiply by u^3 again, then 
you get a number of norm 7:

   111586 + 20721*sqrt(29)

And each time you multiply by u^6 = 9801 + 1820*sqrt(29), you get another 
solution. So this is how you get from one solution (x, y) to another 
(9801x + 1820*29y, 1820x + 9801y).

You can also run this recurrence backwards by multiplying by 
u^-6 = 9801 - 1820*sqrt(29), which ends up getting you the same answers, 
but with the sign of y changed. You can also multiply by -1, which is the 
same as changing the sign of both x and y.

So does that clear up your confusion? Feel free to write back if you have 
more questions.

- Doctor Vogler, The Math Forum
  

Date: 02/10/2016 at 11:28:59
From: Ian
Subject: Thank you (Solutions greater than 1000 to x^2 - 29y^2 = 7)

Dear Doctor Vogler,

All is clear now. As you were kind enough to explain: Norm(u) was -1!
Associated Topics:
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/