Olympiad Maths Prep

Track / Stage 7 / 77 of 300 #1477 of 2000

Problem 1477

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.1 Prove it

Theorem 7 Let ξ0\xi_{0} be an irrational number. If there is a rational fraction a/b,b1a / b, b \geqslant 1, such that
ξ0a/b<1/(2b2),\left|\xi_{0}-a / b\right|<1 /\left(2 b^{2}\right),

then a/ba / b must be one of the convergents of ξ0\xi_{0}.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Solving according to formula (13) we get
8=2+(82)=2+4/(8+2)=2,(8+2)/4=2,1+(82)/4=2,1,8+2=2,1,4+(82)=2,1,4,(8+2)/4\begin{aligned} \sqrt{8} & =2+(\sqrt{8}-2)=2+4 /(\sqrt{8}+2) \\ & =\langle 2,(\sqrt{8}+2) / 4\rangle \\ & =\langle 2,1+(\sqrt{8}-2) / 4\rangle=\langle 2,1, \sqrt{8}+2\rangle \\ & =\langle 2,1,4+(\sqrt{8}-2)\rangle \\ & =\langle 2,1,4,(\sqrt{8}+2) / 4\rangle \end{aligned}

This returns to the case of 2,(8+2)/4\langle 2,(\sqrt{8}+2) / 4\rangle, therefore, the numbers repeat, yielding
8=2,1,4,1,4,1,4,.\sqrt{8}=\langle 2,1,4,1,4,1,4, \cdots\rangle .

We also obtain (why)
(8+2)/4=1,4,1,4,1,4,8+2=4,1,4,1,4,1,\begin{array}{l} (\sqrt{8}+2) / 4=\langle 1,4,1,4,1,4, \cdots\rangle \\ \sqrt{8}+2=\langle 4,1,4,1,4,1, \cdots\rangle \end{array}

Proof: Without loss of generality, assume (a,b)=1(a, b)=1 (why). From formula (3) in §2, we know there exists a unique nn such that
knb<kn+1k_{n} \leqslant b<k_{n+1}

First, we prove that b=knb=k_{n}. If not, there must be
kn<b<kn+1k_{n}<b<k_{n+1}

and a/ba / b is not a convergent fraction (why), thus
hn/kna/b1/(bkn).\left|h_{n} / k_{n}-a / b\right| \geqslant 1 /\left(b k_{n}\right).

From b<kn+1b<k_{n+1}, Theorem 6(i) implies
ξ0knhnξ0ba,\left|\xi_{0} k_{n}-h_{n}\right| \leqslant\left|\xi_{0} b-a\right|,

Thus, from equations (30), (31), and condition (27), we get
1/(bkn)hn/kna/bξ0hn/kn+ξ0a/b<1/(2bkn)+1/(2b2)\begin{aligned} 1 /\left(b k_{n}\right) & \leqslant\left|h_{n} / k_{n}-a / b\right| \leqslant\left|\xi_{0}-h_{n} / k_{n}\right|+\left|\xi_{0}-a / b\right| \\ & <1 /\left(2 b k_{n}\right)+1 /\left(2 b^{2}\right) \end{aligned}

From the above inequality, we deduce b<knb<k_{n}, which is a contradiction. Therefore, b=knb=k_{n} must hold. Furthermore, from the right half of the above inequality (which is valid due to condition (27) and equation (31)), we get
hn/kna/kn<1/kn2,\left|h_{n} / k_{n}-a / k_{n}\right|<1 / k_{n}^{2},

which implies hna<1/kn\left|h_{n}-a\right|<1 / k_{n}. Thus, a=hna=h_{n}. Therefore, a/b=hn/kna / b=h_{n} / k_{n} is a convergent fraction of ξ0\xi_{0}. Proof completed.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.