### Calculating the backward continued fraction of a quadratic irrational

This program finds the backward continued fraction expansion of a quadratic irrational α = (u + t√d)/v, where d,t,u,v are integers, d >1, and nonsquare, t and v nonzero.

With ξ_{0} = α, for i ≥ 0, a_{i} = int(ζ_{i}) + 1 and ζ_{i+1} = 1/(a_{i} - ζ_{i}), we get a finite continued fraction which eventually becomes periodic

where a_{i} ≥ 2 for i ≥ 1.
Here a quadratic surd α is *reduced* if α > 1 > α' > 0 and these are the surds which have a purely periodic continued fraction expansion. See implementation as a BC program.

This continued fraction is mentioned in F. Hirzebruch's paper *Hilbert modular surfaces*, L'Enseignement Math. **19** (1973) and a paper by Don Zagier, *A Kronecker Limit Formula for Real Quadratic fields*, Math. Ann, **213**, 153-184 (1975) especially pages 177-183.
Also see *Zetafunktionen und quadratische Körper, Eine Einführung in die höhere Zahlentheorie*, Don Zagier, Springer 1981.

Hirzebruch on page 241 proved that if p=4n+3 is a prime and h(p) = 1, then h(-p) = (a_{1} + ··· + a_{r})/3 - r, where r is the period length of the least integer continued fraction of √p.

Here h(p) is the class number of the real quadratic field ℚ(√p) and
h(-p) is the class number of the imaginary quadratic field ℚ(√-p).

Hirzebruch also noted that h(-p) = (-b_{1}+b2 - ··· + b_{2s})/3, where the b_{i} are partial quotients of the simple continued fraction expansion of √p and 2s is the period length.

The convergents A_{i}/B_{i} are calculated as follows:

A_{-1} = 1, B_{-1} = 0, A_{0} = a_{0}, B_{0} = 1,

A_{i} = a_{i}A_{i-1} - A_{i-2},
B_{i} = a_{i}B_{i-1} - B_{i-2}, i ≥ 1.

We first convert α to (P + √d)/Q, where Q divides d - P^{2} and gcd(P, Q, (d - P^{2})/Q) = 1.

We print the partial quotients a_{n}, the convergents A_{i}/B_{i} and complete quotients ζ_{i} with the period partial quotients in bold font.

*Last modified 23rd November 2011*

Return to main page