Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$$

share|cite|improve this question
It could very well go back to Lagrange, or even to Euler. – André Nicolas Mar 1 '12 at 22:48
up vote 3 down vote accepted

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 $$ (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).

share|cite|improve this answer
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? – Jason Smith Mar 2 '12 at 0:50
@Jason What proof in 2000 do you refer to? – Bill Dubuque Mar 2 '12 at 1:30
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. – Jason Smith Mar 2 '12 at 16:40
@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. – Bill Dubuque Mar 2 '12 at 17:07

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.

share|cite|improve this answer
Ok definition of an algorithm but thank you. – Jason Smith Mar 1 '12 at 22:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.