Maths Olympiad Prep

Library / /496 of 520

Number theory Difficulty 7.3 National olympiad, round 2 Prove it

Theorem 7 Let α\alpha be a real number, then for any positive number x1x \geqslant 1, there exist integers a,ba, b, satisfying
1bx,(a,b)=1,1 \leqslant b \leqslant x, \quad(a, b)=1,

such that
αa/b<1/(bx)|\alpha-a / b|<1 /(b x) \text {. }

Solution

Prove: The following [x]+2[x]+2 numbers
1,jα[jα],j=0,1,,[x]1, \quad j \alpha-[j \alpha], \quad j=0,1, \cdots,[x]

are all in the interval [0,1][0,1], and thus by the pigeonhole principle, there must be two numbers whose difference does not exceed ([x]+1)1([x]+1)^{-1}. If these two numbers are
j1α[j1α],j2α[j2α],0j1<j2[x],j_{1} \alpha-\left[j_{1} \alpha\right], \quad j_{2} \alpha-\left[j_{2} \alpha\right], \quad 0 \leqslant j_{1}<j_{2} \leqslant[x],

then we take d=j2j1,c=[j2α][j1α]d=j_{2}-j_{1}, c=\left[j_{2} \alpha\right]-\left[j_{1} \alpha\right] and
a=c/(c,d),b=d/(c,d).a=c /(c, d), \quad b=d /(c, d) .

Otherwise, these two numbers must be
1,j1α[j1α],0j1[x]1, \quad j_{1} \alpha-\left[j_{1} \alpha\right], \quad 0 \leqslant j_{1} \leqslant[x]

In this case, we take d=j1,c=[j1α]+1d=j_{1}, c=\left[j_{1} \alpha\right]+1 and
a=c/(c,d),b=d/(c,d).a=c /(c, d), \quad b=d /(c, d) .

It is easy to verify that, in either case, the chosen a,ba, b satisfy equation (10), and
αa/b1/(b([x]+1)),|\alpha-a / b| \leqslant 1 /(b([x]+1)),

from which it follows that equation (11) holds. Proof complete.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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