SOLVING INTEGRAL QUADRATICS INTEGRALLY AND RATIONALLY.
[Based on supplemental handout for a class in Elliptic Curves
Dave Rusin, rusin@math.niu.edu Last revised 2/3/95 ]
Sect I. INTRODUCTION
Suppose given an integral quadratic equation
a x^2 + b xy + c y^2 + dx + ey + f = 0
Our goals are:
(1) To prove the Hasse-Minkowski Theorem (local-to-global principle):
that this equation has rational solutions iff it is
solvable in R and in each of the p-adic fields Q_p.
(In one direction this is trivial.)
(2) To determine when the equation has integral solutions and to find a
procedure to determine all integer solutions quickly.
We do this by reducing the equation (in most cases) to a
Pellian equation x^2 + D y^2 = N.
(3) To provide comments and extensions relating this to other topics.
(4) To provide source code for solving these problems
(not yet done)
Sect II. REDUCTION TO THE PARTICULAR (PELLIAN) FORM
The equation
b xy + dx + ey + f = 0
is linear (and so, well-understood) if b=0; if b<>0, we can get an equivalent
equation my multiplying by b then rearranging to get
( b x + e ) ( b y + d ) = ( de - bf)
This is easy to deal with if de=bf. Otherwise, bx+d has to be a factor of
de-bf, of which there are only finitely many. So we choose a factor g
(positive or negative) and then solve for x and y in
b x + d = g
b y + e = g' = (de-bf)/g
In particular, it is easy to spot which solutions (x,y) are integral.
(The equation over a field is essentially XY=1, that is, it clearly has
solutions in R and every Q_p, and it has solutions in Q).
Having dispensed with this case, we may assume that one of the squares,
say x^2, has a non-zero coefficient. Assuming a<>0 we multiply our
original equation by 4a and get an equivalent equation involving
x1 = 2a x + b y + d
and y, namely
x1^2 + (4ac-b^2) y^2 + (4ae-2bd) y + (4af-d^2) = 0
If (x,y) is an integral solution to the original equation, (x1,y)
will be an integral solution to this one; the converse is only true
for those integral solutions (x1,y) in which x1 -by = d mod (2a).
Over any field, the solutions (x,y) and (x1,y) are in bijection.
We write the last equation in the form
x1^2 + D y^2 + E y + F = 0.
If D = 0, there can only be an integral solution if -F is a square
mod E; then all integral solutions are found by taking u to be each
of the (finitely many) possible square roots of -F mod E, taking
x1 = u + E x2 (for any integer x2), and then taking
y = -E x2^2 - (2u) x2 - [(u^2+F)/E] (an integer).
(Over a field, this equation is essentially X^2+Y=0, which has solutions
over every R and Q_p, and solutions over Q).
(If both D and E are zero, it is easy to analyze the solutions to
x1^2+F=0 over the integers, rationals, R, or Q_p).
Excluding this case, we may now assume D is nonzero. We don't change
the solution set if we multiply by 4D; this gives an equation in
y1 = 2D y + E
and x1 which may be written
y1^2 + (4D) x1^2 = (E^2- 4DF).
As before, if we had integer solutions (x1,y) to the previous equation,
we get integer solutions (x1,y1) to this one; integer solutions to
this one only give integer solutions to the previous one if y1 = E mod 2D.
Solutions over a field to the two equations are again in bijection.
The equation to be solved now has the form
y1^2 + D0 x1^2 = N0
for integers D0 and N0. We will look for rational solutions first,
then return to look for integral solutions. Observe that in what
follows we may assume x1 and y1 are non-negative; arbitrary changes
in sign provide more solutions.
Sect III. PROOF OF THE HASSE-MINKOWSKI THEOREM
We wish to determine whether the quadratic equation has rational solutions.
In this case we yield to the encumbrances of invertibility. Observe that
a rational solution exists iff there is a solution in integers to
y2^2 + D0 x2^2 = N z2^2
and that if any integer solution exists, a solution exists with x2, y2, and
z2 relatively prime.
Write D0=S^2 D1 and N0=T^2 N1 with D1 and N1 squarefree. Let
G = gcd(D1, N1) and D1= G D2 and N1 = G N2. Note that D2 and N2 are
relatively prime to each other and to G. Now, multiply the equation to
be solved by G to get and equation involving
x3=S G x2
y3=G y2
z3=T G z2
namely
G y3^2 + D2 x3^2 + (-N2) z3^2 = 0
which we will rewrite with more symmetric notation as
(*) a1 x1^2 + a2 x2^2 + a3 x3^2 = 0
where the ai are pairwise relatively prime nonzero integers. Our task is
to show that if this equation has a solution in Z_p for all primes p,
it has a rational solution. Note that we can assume at least one xi is
not divisible by p by dividing by gcd(x1, x2, x3) (which is a power of p).
Actually, we don't care about solvability in Q_p for odd p not
dividing any ai. We also don't need to know it's solvable in both R
and Q_2. Cassel's book gives a proof assuming solvability in Q_2.
Here is a proof (from Borevich and Shafarevich, Number Theory) which
assume solvability in R.
First let's see what we learn from assuming (*) is solvable in
Q_p for a prime p.
Suppose p is a prime dividing a1. Choose a solution to this
last equation in Z_p. I claim p does not divide x2. For if p|x2,
then we'd have p| a3 x3^2, whence p | x3^2, so p|x3, so p^2 would
divide a2 x2^2 + a3 x3^2 and thus a1 x1^2, so (as p divides a1 only
to the first power) p|x1^2 and then p|x1. But this would make p divide
all of x1, x2, and x3, contrary to our hypothesis. So we have p not dividing
x2 (nor, by symmetry, x3). Then division mod p is defined so that we
may write -(a2/a3) = (x3/x2)^2 mod p. Now, the right side is the square
of a integer in Z_p (mod p), but the congruence classes mod p are just
the congruence classes of integers mod p. It follows that there is an
integer S=S1(p) such that -a2/a3 = S^2 mod p, i.e. a2 + S^2 a3 = 0.
Then (*) reduces, mod p, to the congruence a3[(S(p) x2)^2 - x3^2]=0
In particular, we may factor the left side of (*) mod p as
[S(p) x2 - x3][a3 S(p) x2 + a3 x3]. (The factorization is unique up to
arrangement of the factors and up to scalar multiplication).
Using the Chinese Remainder Theorem, we may find an integer S1 congruent
to S(p) mod p for each p | a1. (S1 is unique mod a1 once the S(p)
are fixed, but that means there are 2^n choices for S1 mod a1 if a1
has n odd prime factors.) Then it must be true that
a1 x1^2 + a2 x2^2 + a3 x3^2 = [S1 x2 - x3][a3 S1 x2 + a3 x3] mod a1
since the congruence holds modulo each p| a1 and a1 is square-free.
Likewise we find integers S2 and S3 so that the left side of (*)
factors as [S2 x3 - x1][a3 S2 x3 + a1 x1] mod a2 and as
[S3 x1 - x2][a1 S3 x1 + a2 x2] mod a3. With another application of the
Chinese Remainder Theorem, we can write down two integral linear
forms L and M so that
a1 x1^2 + a2 x2^2 + a3 x3^2 = L(x1, x2, x3).M(x1, x2, x3) mod A,
where in what follows we will write A for a1 a2 a3.
In particular, if (x1, x2, x3) is any triple of integers where
L(x1, x2, x3) = 0, then the left side of (*) is a multiple of A.
The set of such solutions is an integer lattice, and an application of
Minkowski's theorem would show that we can find one which will make
the left side of (*) actually be zero. But we can do this more
directly as follows.
Consider the box defined by the inequalities |ai| xi^2 < |A| and
xi >= 0 for i=1, 2, 3. The number of possible solutions xi is
ceiling(sqrt(|A|/|ai|)), which is strictly greater than sqrt(|A|/|ai|)
So the number of triples we are considering is strictly greater than
the product of these, which is |A|. (OK, I lied a little: the number is
only _strictly_ greater if the |A|/|ai| are not all squares. Since the
ai are relatively prime, this is sure to hold unless |ai|=1 for all i.
But this case is easily handled.)
In particular, by the pigeonhole principle, there must be a pair of
triples giving values to L(x, y, z) which are congruent mod A, and
thus (by substracting) we find an integral triple (x,y,z) making L a
multiple of A. Then, as in an earlier paragraph, the left side of (*)
is also a multiple of A there.
Note that (x,y,z) need not be in the box, but it's easy to see
(|x|, |y|, |z|) must be, so this is now a point in the box where (*) is
a multiple of A .
Now, we have not yet used the fact that the equation (*) is assumed solvable
in R. This assumption is equivalent to the statment that the ai don't
all have the same sign. Multiplying through by -1 and relabelling the
variables, as needed, we can assume a1, a2 > 0 > a3. Then it's easy to
see that for any (x,y,z) in the box, the left side of (*) is strictly
between -|A| and 2|A|. In particular, if it's an integer multiple of A,
it's either 0 or |A|.
In the latter case, we use this trick: if
a1 x1^2 + a2 x2^2 + a3 x3^2 = A = -a1 a2 a3,
then a1 z1^2 + a2 z2^2 + a3 z3^2 =0
where z1= x1 x3 + a2 x2
z2= x2 x3 - a1 x1
z3= x3 x3 + a1 a2
(This is another point in the lattice.)
So, one way or another, we have found an integer triple making (*) hold.
Sect IV. COMMENTS ON PROOF AND APPLICATION OF THE H-M THEOREM
It is worth contemplating the effectiveness of this proof.
If we can factor some integer coefficients, we can transform the arbitary
quadratic into Sum ai xi^2 = 0. We only used the existence of a
solution in Q_p to show that each -(ai/aj) is a square modulo
the primes dividing the other ai. This is easily checked anyway, and in
fact fast algorithms for computing square roots mod p exist. Thus the
form L above is easily computed, and we may consider the solution set
L=0 (a lattice) to be known. Indeed it will have very few points
within the box (since the volume comes so close to the index); it is
not hard to seek the lattice points closest to the origin. (If all else
fails, we have given explicit upper bounds on the |xi|.) These points will
solve the original equation. There may be more solutions, and indeed, we
have quite a bit of freedom in constructing the lattice (any choice of which
will lead to a solution): for, modulo each odd prime in question we have
two choices of S(p).
Interestingly, if the coefficients of the problem are very large it may
be impossible to factor the necessary terms, and indeed difficult even
to find the square-free ai. (Relatively primality is easier.) Moreover,
if the ai cannot be factored, it is not so easy to compute square roots
modulo ai. In this case, it seems reasonable to find an integer solution
only when solutions in each Z_p are given. I'm not sure just how effective
this approach is.
It is also worth noting that we can get all the rational solutions once
we have one. Indeed, suppose
y1^2 + D0 x1^2 = N0
for some rational numbers (x1,y1). Any other rational pair may be written
( x1 + t, y1 + m t ) for some m and t (except for (x1, -y1), the only
other solution with the same x coordinate as (x1, y1).) Substituting
into the desired equation, we see the condition that this be a solution with
t <> 0 is that
t =-2 ( y1 m + D0 x1 ) / (m^2 + D0 )
[The case in which the denominator may be zero is trivial.] Thus, all
remaining rational solutions are obtained from the one by selecting arbitary
rational m and obtaining the point
x = x1 -2 ( y1 m + D0 x1 ) / (m^2 + D0 )
y = y1 -2m ( y1 m + D0 x1 ) / (m^2 + D0 )
Of course, the search for _rational_ solutions to a quadratic need not
take longer than the search for _integer_ solutions. We will show now that
this is reasonably fast in some cases.
Sect V. FINDING INTEGRAL SOLUTIONS TO PELL'S EQUATIONS
We seek to solve y1^2 + D0 x1^2 = N0 in integers. This will, in
non-trivial cases, require the use of algebraic number theory.
If D0 is positive and N0 is negative, there are no
solutions in R, hence none in Z or Q.
If D0 is positive and N0 is >=0, there is at most a finite number
of integer solutions to this problem, easily found (for N0 small) by
examining each possible x1 = 0 thru sqrt(N0/D0). Alternately, one
may proceed using algebraic number theory as below.
If D0 is negative, we have the classic Pell's equation. We must show
how to compute integral solutions (when they exist).
We will let D2 = -D0 to focus on signs a little better: D2 > 0. We
will assume as before that D2 is square-free (replacing D2 by D2/S^2
and x1 by S x1 as necessary.)
The critical observation here is that a solution to
y1^2 - D2 x1^2 = N0
in integers is equivalent to the discovery of an element
u=y1 + d x1
in the ring of integers Z[d] of the algebraic number field Q[d] (where
d = Sqrt(D2) ) which has a norm equal to N0. Here the Norm map is just
N(u) = u . ubar
for any such u, where 'bar' is the function sending d to -d
(so ubar = y1 - d x1).
Thus, for general N0, this becomes a problem in algebraic number theory.
The _existence_ of integral solutions may be analyzed as follows. It is
necessary and sufficient to find elements u and ubar in the ring
with u.ubar= N0. I claim this is equivalent to finding a principal ideal
I in the ring such that I.Ibar = (N0) (the principal ideal generated by N0.)
Indeed, if u exists, let I = (u). Conversely, if such an I = (u) exists,
then (u.ubar) = (N0), so u.ubar = N0.v for some unit v in the ring.
But it is clear that v=Norm(u)/N0 lies in the ground field Q, and the
only rational integral units are +- 1. If u.ubar = N0, we are done. If
u.ubar=-N0, then either there is a unit e with e.ebar=-1 (in which
case (ue).(ue)bar = N0 ) or not (in which case the equation u.ubar=N0 has
no solution [I think]). Observe also that we can recover _all_ the solutions
u for which (u) = I if we can find one, by taking u'=uv for all units v.
[*NOTE* I thought wrong. See correction below from John Robertson --djr]
Now, the ideal (N0) may be uniquely factored into prime ideals; indeed,
if N0 = Prod pi^ei, then (N0) = Prod (pi)^ei. These ideals (pi) will
behave in one of three ways: (pi) = Pi (a prime ideal in the ring);
(pi)=Pi.Pi-bar (the prime splits) or (pi)=Pi^2 (the prime ramifies).
It is easy to check the behaviour of any individual pi by checking
to see whether or not D2 is a square mod pi. Thus (N0) may be written
as a product of conjugate ideals iff ei is even for each pi which
stays prime in the ring. In that case, the set of all possible ideals I
such that I.Ibar = (N0) is found by computing all products I = I1 I2 I3
where I1 = Prod (pi)^(ei/2) (the product running over all i with (pi) prime)
I3 = Prod (Pi)^ei (the product over all ramified primes) and
I2 = Prod (Pi)^ei (the product over all split primes, where either Pi or
Pi-bar chosen for each i; that is, there is more than one possible I2).
Given this information, the only impediment to the preceding paragraph is
that the created ideal I is supposed to be principal. This requires a
calculation in the class group of the ring. A solution exists iff some
choice of I2 leads to the identity element in the class group.
The _computation_ of a solution seems to require factoring N0, analyzing
the decomposition of the pi, and studying the class group of the ring.
However, if N0 is less than 2Sqrt(D2), then a solution exists iff it is
discovered via the continued fraction method described below; this does
not require factoring N0 (or D2).
The computation of the set of _all_ solutions involves the computation of
a basic set as above, together with the computation of units. It is known
that the units of this ring are all of the form (+-) e^n where n is
any integer and e is a _fundamental unit_ (the smallest unit > 1). Since
the norm of a unit is a unit in Z (i.e., +1 or -1), we are led to consider
the equations
y1^2 - D2 x1^2 = +-1.
If we have a solution to this, then | (y1/x1) - Sqrt(D2) | =
1/[x1^2.|(y1/x1) + Sqrt(D2)|] (in fact, this is equivalent to the
previous problem up to a loss of sign). For positive x1 and y1, this
implies |(y1/x1) - Sqrt(D2)| is bounded by 1/2x1^2. It is known that
this implies (y1/x1) is one of the recurrent terms in the continued
fraction algorithm computing Sqrt(D2). It can be shown that the first
solution which occurs in this way is a fundamental unit. (In particular,
it will be clear whether or not there are units with norm -1. )
Thus an effective solution exists to find the units of the ring.
(Along the way we discover solutions to the equation
y1^2- D2 x1^2 = N0
for all N0 less than Sqrt(D2) for which a solution does exist.)
I am not familiar with the methods used for the computation of the class
group of real quadratic fields, nor the computation of which element
of the group each ideal pertains to. Thus I can't give an effective
solution to the general Pellian equation. Surely, however, this is known.
One can show that if any solution exists (with x1>0, y1>0, say) then
one exists with x1+y1Sqrt(D2) < Sqrt(N0.e) where e is the fundamental
unit. See Borevich + Shafarevich p 123. I believe
there is also some sort of reduction which reduces the question
for general N0 to those N0 < 2sqrt(D), which is then addressed with
continued fractions, but I can't remember what it is.
You may wish to verify a few examples of various aspects of this theory:
(1) x^2-3y^2 = 11 has no solutions though x^2-3y^2=-11 does
(failure of existence of unit with norm -1)
(2) the pairs (8,1) and (164,25) are solutions to
x^2-43 y^2 = 21 which are not associates (one = other x a unit).
(Two choices of ideal I with I.Ibar = (N0): I=P1.P2 or P1.P2-bar).
(3) 7^2-10.1^2=39 but x^2-10y^2 =N has no solutions for
N=+-3, +-13 (failure of being principal ideals)
(4) In Z[Sqrt(79)] the primes dividing (3) and (5) are
non-principal ideals. Here (3)=P.Pbar where P = (3, 1+sqrt(79))
and 5=Q.Qbar where Q = (5, 2+sqrt(79)). Therefore, (15)=I.Ibar
in two essentially distinct ways, as in example (2). As in example (3),
one of these is principal, so x^2-79 y^2 = +-N is solvable for N= 15
but not for N=3, 5. Unlike that example, though, we must choose I
carefully: P.Q = ( 8-sqrt(79) ), but P.Qbar is not principal.
(The class number is listed as 3, so [P] is of order 3, so
[P][Q]=1 => [P][Qbar]=[P][Q]^(-1) is not 1.)
References:Wagon, Amer Math Monthly 97 (1990) 125-
Hardy, Muskat, Williams, Kath Comp 55 (1990) 327-343
D.A. Cox, 'Primes of the Form x^2+ny^2", Wiley 1989
Sect VI. COMMENTS AND EXTENSIONS
(1) We assumed solutions in Q_p at the outset; however, once we have
reduced to the form Sum(ai xi^2) = 0 with relatively prime squarefree
nonzero ai, this is equivalent to having a solution in Z/pZ.
(2) Yes, this can all be done over other algebraic number fields. The theorem
then is that a solution in the field exists iff solutions exist in all
completions of the field (Q_P for P a prime ideal, and all embeddings
into C ). The initial reduction still works to show that integral solutions
are related to those of x^2 - D y^2 = N, and those solutions may be found
by considering ideals in an extension ring; however, the structure of the
group of units becomes more complex and, as far as I know, there is no
analogue of the continued fraction approach.
(3) I have commented that solving quadratic equations by this method
requires being able to factor integers (something which is implicit in
the presentation of solutions in each Z_p, I suppose). A subsidiary
question is of independent interest: given an integer a can we at
least compute the squarefree part a/s^2? As far as I know this is no
easier than the full factorization problem.
On the other hand, solutions to quadratic polynomial equations by
non-factoring methods (such as the continued fractions algorithm) leads
to methods of factoring. Clearly, a solution of xy=D or x^2-y^2=D
leads to a factorization of D; but also a solution of x^2-D y^2 = 1
has (x+1)(x-1) = D y^2 so gcd(x+1,D) gives a proper factor of D
unless x = +-1 mod D. (Computation of a fundamental unit in Z[Sqrt(D)]
thus provides such a factorization. Unfortunately, this can take roughly
as many steps as a brute-force factorization of D.)
(4) The H-M theorem also holds for quadratics of more than 2 variables.
(5) The H-M theorem does NOT hold for polynomials of higher degree than 2.
Classic counterexamples include products such as
(x^2 + 3 y^2 - 17 z^2) (x^2 + 5 y^2 - 7 z^2)
and Selmer's example
3 x^3 + 4 y^3 + 5 z^3
Loosely, the invariant Sha of an elliptic curve measures the extent of
the failure of the local-to-global principle.
Birch has shown the following: given an odd number d
there is an n so that every homogeneous equation of degree d in
n variables has a nontrivial rational solution.
Sect VII. SOURCE CODE
In an attempt to stay elementary I will write in BASIC the routines
necessary to carry out these calculations.
[not yet done]
==============================================================================
Date: Mon, 29 Dec 1997 10:31:43 -0300
From: Dario Alejandro Alpern
To: rusin@math.niu.edu
Subject: Solving integer quadratic equations in two variables
I'm making a calculator to solve this problem, and I'm using the
information found in your page:
[This page -- djr]
One mistake I found was the following:
> Sect II. REDUCTION TO THE PARTICULAR (PELLIAN) FORM
>
> The equation
> b xy + dx + ey + f = 0
> is linear (and so, well-understood) if b=0; if b<>0, we can get an
equivalent
> equation my multiplying by b then rearranging to get
> ( b x + d ) ( b y + e ) = ( de - bf)
> This is easy to deal with if de=bf. Otherwise, bx+d has to be a
factor of
> de-bf, of which there are only finitely many. So we choose a factor g
> (positive or negative) and then solve for x and y in
> b x + d = g
> b y + e = g' = (de-bf)/g
> In particular, it is easy to spot which solutions (x,y) are integral.
> ...
"bx + d" must be replaced by "bx + e", and "by + e" must be replaced by
"by + d".
I almost finished the calculator except for the following. Is there an
easier way to solve
y1^2 - D2 x1^2 = N0
for N0 > 2sqrt(D2) than the method you wrote?
Now I'm doing the calculator in UBASIC. When I finish I will migrate the
code to JavaScript, so I the calculator can be used online.
Thanks in advance.
--
Dario Alejandro Alpern
Buenos Aires - Argentina
http://members.tripod.com/~alpertron (en castellano)
http://members.tripod.com/~alpertron/ENGLISH.HTM (English)
Si su navegador no soporta JavaScript:
http://members.tripod.com/~alpertron/INDEX2.HTM
If your browser does not support JavaScript:
http://members.tripod.com/~alpertron/ENGLISH2.HTM
Antes era fanfarron... Ahora soy perfecto!!
==============================================================================
Date: Sun, 4 Jan 1998 02:25:51 -0600 (CST)
From: Dave Rusin
To: alpertron@hotmail.com
Subject: Re: Solving integer quadratic equations in two variables
Thanks for catching the misprints. I believe there are also some sign
errors later (or else I may have confused D0 and D2).
Yes, there are other ways to solve the Pell equation. I'm pretty sure that
Henri Cohen's book has a detailed discussion of this, but it occupies a
major portion of Gauss's Disquisitiones Arithmeticae too! I don't recall
the specifics, but the procedure runs recursively; I believe the idea is
to solve x^2-Dy^2=N by first solving mod N to get x^2-Dy^2=kN for some
k < N; then it suffices (I think) to solve x^2-Dy^2=k, because there's
some way to combine the two solutions to get a solution to x^2-Dy^2=N.
I'm a little hesitant because I think this idea might require Z[sqrt(D)] to
be a unique factorization domain, but there's some way to get around that
problem too I suppose. If the ring is even a little more special (a
Euclidean domain), you can make this procedure go very quickly; see
http://www.math.niu.edu/~rusin/known-math/97/2squares.comp
You don't have to confront the algebraic number theory to solve the problem,
but you do have to realize that it's hiding there, preventing some equations
from having solutions at all; so you might as well accept its presence!
(Note: In order to solve mod N you'll need to be able to factor N, and then
k as well. This is the major bottleneck with the algorithm I described,
and it's unavoidable unless everybody has been blind to a simple
algorithm for factoring integers!)
You can actually find code for this if you have access to maple, since you
can print the isolve procedure, which is capable of finding all solutions
to an integral quadratic in two variables.
Besides Cohen's excellent book and the article by Wagon which is in the
file you have already read, you might want to read a few related notes
at my site and the papers and books they cite. Try scanning
http://www.math.niu.edu/~rusin/known-math/index/11DXX.html
for "Pell" or "quadratic".
dave
==============================================================================
From: Jpr2718@aol.com
Date: Mon, 24 Mar 2003 21:37:23 EST
Subject: Pell equations
To: rusin@math.niu.edu
Dear Dave,
At , in about the middle, you say,
``If u.ubar = N0, we are done. If u.ubar=-N0, then either there is a unit e
with e.ebar=-1 (in which case (ue).(ue)bar = N0) or not (in which case the
equation u.ubar=N0 has no solution [I think]).''
Actually, there are counterexamples to this statement. For instance, x^2 -
34y^2 = -1 does not have integer solutions, but both x^2 - 34y^2 = 33 and x^2
- 34y^2 = -33 have solutions ((13, 2) for the first, and (1, 1) for the
second).
For some methods for solving the generalized Pell equation x^2 - Dy^2 = N see
http://hometown.aol.com/jpr2718/.
John Robertson
jpr2718@aol.com