194 IV Continued Fractions and Their Uses
The proof of Proposition 7 shows that the period is at mostg(g+ 1 )/2 and thus is
certainly less thanD. By counting the pairs of integersA,Bfor which not only
0 <√
D+B< 2 A<
√
D−B,
but alsoD≡B^2 mod 4A, it may be shown that the period is at mostO(
√
DlogD).
(TheLandau order symbolused here is defined under ‘Notations’.)
Proposition 8A real numberξis a quadratic irrational if and only if its continued
fraction expansion is eventually periodic.
Proof Suppose first that the continued fraction expansion ofξ is eventually peri-
odic. Then some complete quotientξmhas a periodic continued fraction expansion
and hence is a quadratic irrational,by Proposition 7. But this implies thatξalso is a
quadratic irrational.
Suppose next thatξis a quadratic irrational. We will prove that the continued
fraction expansion ofξis eventually periodic by showing that some complete quo-
tientξn+ 1 is reduced. Since we certainly haveξn+ 1 >1, we need only show that
− 1 <ξn′+ 1 <0. Butξ′=ξandξ′=(pnξn′+ 1 +pn− 1 )/(qnξn′+ 1 +qn− 1 ). Hence, by
Lemma 0,− 1 <ξn′+ 1 <0 for all largen.
It follows from Proposition 8 that any real quadratic irrational is badly approx-
imable, since its partial quotients are bounded. It follows from Propositions 7 and 8
that there are only finitely many inequivalent quadratic irrationals with a given dis-
criminantD>0, since any real quadratic irrational is equivalent to a reduced one and
only finitely many pairs of integersA,Bsatisfy the inequalities
0 <√
D+B< 2 A<
√
D−B.
Proposition 8 is due to Euler and Lagrange. It was first shown by Euler (1737) that
a real number is a quadratic irrational if its continued fraction expansion is eventually
periodic, and the converse was proved by Lagrange (1770). Proposition 7 was first
stated and proved by Galois (1829), although it was implicit in the work of Lagrange
(1773) on the reduction of binary quadratic forms. Proposition 7 provides a simple
proof of the following result due to Legendre:
Proposition 9For any real numberξ, the following two conditions are equivalent:
(i)ξ> 1 ,ξis irrational andξ^2 is rational;
(ii)the continued fraction expansion ofξhas the form[a 0 ,a 1 ,...,ah],whereah=
2 a 0 and ai=ah−ifor i= 1 ,...,h− 1.
Proof Suppose first that (i) holds. Thenξis a quadratic irrational, since it is a root of
the polynomialt^2 −ξ^2. The continued fraction expansion ofξcannot be periodic, by
Proposition 7, sinceξ′=−ξ<−1. However, the continued fraction expansion ofξ 1
is periodic, sinceξ 1 >1and1/ξ 1 ′=ξ′−a 0 <−1. Thusξ 1 =[a 1 ,...,ah]forsome
h≥1. By Proposition 7 also,
− 1 /ξ 1 ′=[ah,...,a 1 ].