Number Theory: An Introduction to Mathematics

2 Diophantine Approximation 185

betweenξand its complete quotientξnit follows that

η=(anξn+bn)/(cnξn+dn),

where

an=apn− 1 +bqn− 1 , bn=apn− 2 +bqn− 2 ,

cn=cpn− 1 +dqn− 1 , dn=cpn− 2 +dqn− 2 ,

and hence

andn−bncn=(ad−bc)(pn− 1 qn− 2 −pn− 2 qn− 1 )=± 1.

The inequalities

|qn− 1 ξ−pn− 1 |< 1 /qn, |qn− 2 ξ−pn− 2 |< 1 /qn− 1

imply that

|cn−(cξ+d)qn− 1 |<|c|/qn, |dn−(cξ+d)qn− 2 |<|c|/qn− 1.

Sincecξ+d>0,qn− 1 >qn− 2 andqn→∞asn→∞, it follows thatcn>dn> 0
for sufficiently largen. Then, by Proposition 1,ξnis a complete quotient also ofη.
Thus the continued fraction expansions ofξandηhave a common tail.

2 Diophantine Approximation

The subject ofDiophantine approximationis concerned with finding integer or
rational solutions for systems of inequalities. For problems in one dimension the
continued fraction algorithm is a most helpful tool, as we will now see.

Proposition 3Let pn/qn(n≥ 1 )be a convergent of the real numberξ.If p,qare
integers such that 0 <q≤qnand p=pnif q=qn,then

|qξ−p|≥|qn− 1 ξ−pn− 1 |>|qnξ−pn|

and

|ξ−p/q|>|ξ−pn/qn|.

Proof It follows from (3) that the simultaneous linear equations

λpn− 1 +μpn=p,λqn− 1 +μqn=q,

have integer solutions, namely

λ=(− 1 )n−^1 (pnq−qnp), μ=(− 1 )n(pn− 1 q−qn− 1 p).

The hypotheses onp,qimply thatλ=0. Ifμ=0, then

|qξ−p|=|λ(qn− 1 ξ−pn− 1 )|≥|qn− 1 ξ−pn− 1 |.