From: jpr2718@aol.com (Jpr2718)
Newsgroups: sci.math
Subject: Re: General Pell equation: x^2 - N*y^2 = D
Date: 03 Jun 1998 01:13:32 GMT

>I'm looking for a process to solve the general Pell equation--even knowing if
>such a process exists would be helpful to me. A reference to a helpful number
>theory book would be most welcome!
>
>

There are a number of processes for solving these equations.  The continued
fraction method solves the equation x^2-dy^2=m for d>0 and m=1 or -1 as
explained in Olds, Continued Fractions, published in the New Mathematical
Library by the Mathematical Association of America, or Niven, Zuckerman and
Montgomery, Intro to Number Theory, 5th edition, or many other elementary
number theory books.  The continued fraction method is also the method of
choice if d>0 is not a square and abs(m)<sqrt(d).  Less well known is that the
continued fraction method, just like for +/-1 also solve the equation for
m=+/-4.  One just tinkers with the initial values a bit.

For other cases, with d>0, essentially abs(m)>sqrt(d), either use a brute force
search up to limits given here and there, or use either the cyclic method or
the method given in Chrystal's Algebra.  The limits for a brute force search
are given correctly in Richard Mollin's Fundamental Number Theory with
Applications and I think also in his book Quadratics.  They are given
incorrectly in Rose's A Course in Number Theory (1st or 2nd editions) and in
Leveque, Topics in Number Theory, vol 1 (I think, it might be vol. 2).  The
incorrect limits are not too hard to fix.  Add zero as a lower bound for the
search, and increase the upper bound on one of these a bit as I recall. 
Essentially solutions fall into families.  If you have one solution, and
generate another from the solution to x^2-dy^2=1, then all other families (if
any) have a solution that lies between these two.  So you just need to search
between two such. If there are no solutions, you'll need to check a reference
to be able to tell when you've searched far enough.  

The cyclic method is explained in Edward's Fermat's Last Theorem.  Chrystal's
Textbook of Algebra gives a recursive method.

Of course Gauss's Disquisitions Arithmeticae covers methods for solving these
equations, but is a slow read.

If you have Excel 6.0 or later for a PC with Windows, I can e-mail you an Excel
file that uses the continued fraction method for the d>0, m=+/-1, +/-4
equations, and uses a search method for all others with d>0, not square.  If
you have Word 6.0 or later for a PC with Windows, I can e-mail you a file that
gives thealgorithm (no proofs) for the continued fraction method for the +/-1
and +/-4 equations.

For d<0 the most practical method is a brute force search. The limits of the
search are easy to work out.   For large coefficients, methods in Cox's Primes
of the Form x^2+ny^2 might be useful.

jpr2718@aol.com


==============================================================================

From: Richard Pinch <rgep@cam.ac.uk>
Newsgroups: sci.math.research
Subject: Re: general Pell equation: x^2 - N*y^2 = D
Date: Thu, 04 Jun 1998 16:02:03 +0100

rhiebert@my-dejanews.com wrote:
> 
> I would like to know if there is a process for solving the general Pell
> equation:
> 
> x^2 - N*y^2 = D
> 
> I know how to do this if D=1 (with the convergents of the continued fraction
> form of sqrt(N)) but I'm going nowhere fast with the general form.

There is a very useful discussion in chapter 7.4 of Edwards "Fermat's
Last Theorem", Springer GTM 50.  The "cyclic method" generalises the
CF method for the case D=1.
-- 
Richard Pinch		Queens' College, Cambridge
rgep@cam.ac.uk		http://www.dpmms.cam.ac.uk/~rgep
==============================================================================

From: jpr2718@aol.com (Jpr2718)
Newsgroups: sci.math
Subject: Re: Procedure to solve General Pellian Equations
Date: 24 Jul 1998 01:57:34 GMT

>I was "playing" with the coefficients of the Pellian equations and I
>found a method to solve them.
>
>
Professor Alpern,

In general, it appears that your method would miss solutions.  For example,
x^2-2y^2=2 has solutions, (2,1), (10,7), ...  Your method suggests looking at
x^2-8y^2=2, which does not have any solutions.  A counterexample closer to your
example is x^2-7y^2=29, which has solutions, while x^2-847y^2=29 has no
solutions.

There are several methods for solving the Pellian equation when |N|>sqrt(d). 
One is to use a brute-force search.  If N<0 then search on y=sqrt(abs(n/d)) to
sqrt((abs(n)(x1+1))/(2d)) and if N>0 search on y=0 to sqrt((n(x1-1))/(2d))
where (x1, y1) is the minimum positive solution (x, y) to x^2-dy^2=1.  If N<0,
for each positive (x, y) found by the search, also take (-x, y).  If N>0, also
take (x, -y).  In either case, all positive solutions are generated from these
using (x1, y1) in the standard way.  See Mollin, Fundamental Number Theory with
Applications, pages 299 and 300 for equivalent formulas.  Note that the
formulas in LeVeque and Rose are not quite right.

Another method is the cyclic method, explained in Chapter 7 of Edward's
Fermat's Last Theorem.  Chrystal, Textbook of Algebra, Part 2, pp 482ff,
describes Lagrange's reduction of the case |N|>sqrt(d) to some number of cases
with |N|<sqrt(d).

John Robertson
jpr2718@aol.com
==============================================================================

From: Kurt Foster <kfoster@rmi.net>
Newsgroups: sci.math
Subject: Re: Procedure to solve General Pellian Equations
Date: 24 Jul 1998 14:16:25 GMT

In <35B886C3.EF40BD0B@hotmail.com>, Dario Alejandro Alpern said:
[snip]
. Jpr2718 wrote:

..  Chrystal, Textbook of Algebra, Part 2, pp 482ff, describes Lagrange's
.. reduction of the case |N|>sqrt(d) to some number of cases with
.. |N|<sqrt(d).

. I don't know this method. Can you explain it?
.
  Chrystal already explains it.  In detail, with examples.  "Textbook of
Algebra" is an old standby, almost a standard reference.  You might be
able to find it in a library (even some public libraries carry it) or a
used-books store.  The most recent publisher I'm aware of was Dover, who
had a 2-volume paperback edition.  There's an older hardcover edition
published by Chelsea, but that may be out of print.
==============================================================================

From: jpr2718@aol.com (Jpr2718)
Newsgroups: sci.math
Subject: Re: Procedure to solve General Pellian Equations
Date: 25 Jul 1998 03:37:18 GMT

 Dario Alejandro Alpern said:

>  Jpr2718 wrote:
>  
>  > >I was "playing" with the coefficients of the Pellian equations and I
>  > >found a method to solve them.
>  > >
>  > Professor Alpern,
>  >
>  > In general, it appears that your method would miss solutions.  For
example,
> 
>  > x^2-2y^2=2 has solutions, (2,1), (10,7), ...  Your method suggests looking

> at
>  > x^2-8y^2=2, which does not have any solutions.  A counterexample closer to

> your
>  > example is x^2-7y^2=29, which has solutions, while x^2-847y^2=29 has no
>  > solutions.
>  >
>  
>  John,
>  
>  Yes, you are right. I think that there should be a better method to find the

> prime
>  number  that squared multiplies D. Maybe using simple modular considerations

> we can
>  avoid those counterexamples.

More complicated counterexamples are possible.  For instance, for x^2-5y^2=4,
the equation x^2-20y^2=4 generates some but not all solutions of the original
equation.  I doubt that for all equations x^2-dy^2=m, |M|>sqrt(d) there always
is a prime p so that solutions to x^2-(dp^2)y^2=m generate all solutions to
x^2-dy^2=m.  In general, I would expect several primes to be necessary, and
that it would be difficult to tell when one had found all solutions.

>  
>  > There are several methods for solving the Pellian equation when
|N|>sqrt(d)
> .
>  > One is to use a brute-force search.  If N<0 then search on
y=sqrt(abs(n/d))
>  to
>  > sqrt((abs(n)(x1+1))/(2d)) and if N>0 search on y=0 to sqrt((n(x1-1))/(2d))
>  > where (x1, y1) is the minimum positive solution (x, y) to x^2-dy^2=1.  If 
> N<0,
>  > for each positive (x, y) found by the search, also take (-x, y).  If N>0, 
> also
>  > take (x, -y).  In either case, all positive solutions are generated from 
> these
>  > using (x1, y1) in the standard way.  See Mollin, Fundamental Number Theory

> with
>  > Applications, pages 299 and 300 for equivalent formulas.  Note that the
>  > formulas in LeVeque and Rose are not quite right.
>  >
>  
>  In this case the number of computations is very high. Consider, for example 
> the
>  equation  x^2 - 991 y^2 = 1. In this case x1 is a 36-digit number and y1 is 
> a
>  35-digit number. Then it would be impossible to perform the brute-search 
> method in
>  this way. With a well-chosen multiplier as I wrote above it could be 
> possible to
>  find solutions in a reasonable amount of time.

I agree that brute force search will not work in cases where coefficients or
solutions to the equation x^2-dy^2=1 are large.  On the other hand, what
guarantee is there that the smallest primeneeded to find a family of solutions
isn't almost as large as the smallest solution to x^2-dy^2=1?

Minor quibble:  I get 30 digits and 29 digits as the lengths of the x and y
that are the smallest positive solutions to x^2-991y^2=1.
x=379516400906811930638014896080,
y=12055735790331359447442538767.

>  
>  > Another method is the cyclic method, explained in Chapter 7 of Edward's
>  > Fermat's Last Theorem.  Chrystal, Textbook of Algebra, Part 2, pp 482ff,
>  > describes Lagrange's reduction of the case |N|>sqrt(d) to some number of 
> cases
>  > with |N|<sqrt(d).
>  >
>  
>  I don' know this method. Can you explain it?

Both of these methods are somewhat complicated, and it's best if you read these
sources.  I would expect both are easily available.  Chrystal was THE college
algebra book in the 1930's I think.  It might be in storage, but any college
math library should have it.  Also, it's a Dover paperback, but I don't know
whether it's still in print.  Edwards' discussion of the cyclic method is more
like 50 pages, so it's best if you find the book.  Cohen's A Course in
Computational Algebraic Number Theory might also be useful for implementing
either of these methods.

>  
>  > John Robertson
>  > jpr2718@aol.com
>  
>  Best regards,
>  --
>  Dario Alejandro Alpern
>
==============================================================================