Number Theory: An Introduction to Mathematics

1 The Continued Fraction Algorithm 183

Proof We h av e

ηn+ 1 =(qn− 1 η−pn− 1 )/(pn−qnη).

Hence

θn+ 1 :=qnηn+ 1 +qn− 1

=(pnqn− 1 −pn− 1 qn)/(pn−qnη)

=(− 1 )n+^1 /(pn−qnη)

=(− 1 )n/qn(η−pn/qn).

Sincepn/qn→ξ=ηandqn→∞, it follows thatθn→0. Since

ηn+ 1 =−(qn− 1 −θn+ 1 )/qn,

we conclude that− 1 <ηn+ 1 <0 for all largen.
Suppose now thatξ>1andη<0. It is readily verified thatηn=an+ 1 /ηn+ 1.
Butan=ξn≥1foralln≥0. Consequentlyηn<0 implies 1/ηn+ 1 <−1and
thus− 1 <ηn+ 1 <0. Sinceη 0 <0, it follows by induction that− 1 <ηn<0forall
n>0.

The complete quotients of a real number may be characterized in the following
way:

Proposition 1Ifη> 1 and

ξ=(pη+p′)/(qη+q′),

where p,q,p′,q′are integers such that pq′−p′q=± 1 and q>q′> 0 ,thenηis a
complete quotient ofξand p′/q′,p/q are corresponding consecutive convergents ofξ.

Proof The relationpq′−p′q=±1 implies thatpandqare relatively prime. Since
q>0,p/qhas a finite continued fraction expansion

p/q=[a 0 ,a 1 ,...,an− 1 ]=pn− 1 /qn− 1

andq=qn− 1 , p= pn− 1. In fact, sinceq >1, we haven >1,an− 1 ≥2and
qn− 1 >qn− 2 .From

pn− 1 qn− 2 −pn− 2 qn− 1 =(− 1 )n=ε(pq′−p′q),

whereε=±1, we obtain

pn− 1 (qn− 2 −εq′)=qn− 1 (pn− 2 −εp′).

Henceqn− 1 dividesqn− 2 −εq′.Since0<qn− 2 <qn− 1 and 0<q′<qn− 1 , it follows
thatq′=qn− 2 ifε=1andq′=qn− 1 −qn− 2 ifε=−1. Hencep′=pn− 2 ifε= 1
andp′=pn− 1 −pn− 2 ifε=−1. Thus

ξ=(pn− 1 η+pn− 2 )/(qn− 1 η+qn− 2 ),

resp.(pn− 1 η+pn− 1 −pn− 2 )/(qn− 1 η+qn− 1 −qn− 2 ).