2
$\begingroup$

I am curious when the following Definition was formulated. Is this a product of Dan Shanks' work?

The following algorithm computes the simple continued fraction expansion of $\frac{P+\sqrt{D}}{Q}$, where $D$ is a nonsquare positive rational and $P$, $Q\neq0$ are any integers. Let $P_0=P$, $Q_0=Q$, and $a_0=\left\lfloor \sqrt{D}\right\rfloor$. For $i\geq1$, define

$$P_i=a_{i-1}Q_{i-1}-P_{i-1} \tag{A}$$

$$Q_i=\frac{D-P_i^2}{Q_{i-1}} \tag{B}$$

$$a_i=\left\lfloor \frac{P_i+\sqrt{D}}{Q_i} \right\rfloor. \tag{C}$$

  • 0
    It could very well go back to Lagrange, or even to Euler.2012-03-01

2 Answers 2

3

It's a well-known ancient algorithm for computing the continued fraction of quadratic irrationals. Below is what Knuth says about the history in TAOCP vol. $2$, solution to exercise $4.5.3.12$ (which contains a complete derivation and proof of correctness)

enter image description here enter image description here

Probably much more can be said on the history. A good place to start is David H. Fowler's The Mathematics of Plato's Academy: A New Reconstruction (which, in addition to history, also provides a nice introduction to the main algebraic properties of continued fractions; see also Chrystal's Algebra).

  • 0
    Bill, Why do you think that the fact that $X^2-PY^2=a$, $P=a^2+(2b)^2$ an odd prime, has integer solutions did not get proved until 2000? It seems that it should have been proved much earlier, considering the proof given by Robertson/Matthews using continued fractions in 2005?2012-03-02
  • 0
    @Jason What proof in 2000 do you refer to?2012-03-02
  • 0
    Feit and Mollin proved this using Algebraic Number Fields. Robertson and Matthews proved in using Continued Fractions. Walsh generalized the result. Mollin has since given a major generalization.2012-03-02
  • 0
    @Jason Perhaps the result was proved earlier, did you check Dickson's History? In any case, there are plenty of simple proofs in elementary number theory that have not been presented simply because they have never been investigated.2012-03-02
2

It's not a definition, it's an algorithm. I first saw it in an early edition of the textbook by Niven and Zuckerman, but I don't know where they might have found it.

  • 0
    Ok definition of an algorithm but thank you.2012-03-01