From: alf@ics.mq.edu.au (Alf van der Poorten)
Subject: Re: Solutions of x^2 - D y^2 = n: history?
Date: 29 Jan 00 15:12:38 GMT
Newsgroups: sci.math.numberthy
Summary: [missing]

Kiran,

I recall Hugh Williams once telling me (after I had alluded to a
`painful process') that this was just `Lagrange's chain of
reductions', so the `history' you want is really no other than the
history of reduction of quadratic forms. Indeed, to check I looked up
what I wrote in `Explicit quadratic reciprocity', in {\it Number
Theoretic and Algebraic Methods in Computer Science, Moscow 1993\/},
Alf van der Poorten, Igor Shparlinski and Horst G. Zimmer eds., World
Scientific 1995, 175--180.

The relevant section, in AMSTeX or AMS-LaTeX, is:

Hugh Williams reminds me that the relevant process is well known --- that
is, known to those who know it --- as `Lagrange's chain of reductions'.
Suppose we have
$X^2-DY^2=d$ with
$|d|>\sqrt D$. I claim that there are integers
$X'$, $Y'$ so that $XY'-X'Y=\pm1$ and ${X'}^2-D{Y'}^2=d'$ with
$|d'|<|d|$. In fact, we see that
$$\pmatrix X&DY\\Y&X\endpmatrix=\pmatrix X&X'\\Y&Y'\endpmatrix
\pmatrix 1&p\\0&d\endpmatrix$$ only determines $p$ mod $d$. We
are in a position to `guess'
$p$ mod $d$ because we know a priori that $d{\mathrel\bigm|}p^2-D$.
Indeed, say using
$pX+dX'=DY$ and
$pY+dY'=X$, we readily obtain ${X'}^2-D{Y'}^2=(p^2-D)/d$, as would have
been dead evident were we thinking about quadratic forms. Thus the
program is to solve $p^2\equiv D\pmod d$ for $\pm p$, whence for an
appropriate choice or choices of $p$ mod $d$,  one may obtain
${X'}^2-D{Y'}^2=d'$, with $|d'|<|d|$ because $|d|>\sqrt D$. Of course
one can iterate this process. We have done nothing more than to construct
a quadratic form of discriminant $4D$, with leading coefficient $d$ and
final coefficient $d'$; in such a way that $|d'|<|d|$.


--------
At round about 23:39 -0500 on 28/01/2000, Kiran S. Kedlaya wrote:


>There is an algorithm for determining the solutions of the equation
>    x^2 - D y^2 = n
>for fixed D squarefree and n any integer, where one successively reduces n
>until it is small enough that one can read off solutions from the
>continued fraction expansion of sqrt(D). I learned about this algorithm
>from Hua's "Introduction to Number Theory".
>
>Question: does this algorithm have an "official" name? And where can I
>read about its history? (Please be specific; a response such as
>"somewhere in Dickson" doesn't help me much.)
>
>Thanks,
>Kiran Kedlaya
>kedlaya@math.mit.edu

------------------------
Alf vdP,
Department of Mathematics
Macquarie University, Sydney 2109  Australia
alf@math.mq.edu.au   phone: +61 2 9850 8947 fax: +61 2 9850 8114
home: +61 2 9416 6026   mobile: +61 4 1826 3129 (from MQ: #6335)