Maths Olympiad Prep

Library / /22 of 70

Algebra Difficulty 8.1 Shortlist Prove it Romania

Let aa and bb be distinct positive real numbers such that na\lfloor n a \rfloor divides nb\lfloor n b \rfloor for every positive integer nn. Show that aa and bb are both integers.

Solution

Since the nb/na\lfloor n b \rfloor / \lfloor n a \rfloor form a sequence of positive integers converging to b/ab/a, it follows that b=mab = m a for some integer m2m \ge 2, and nb=mna\lfloor n b \rfloor = m \lfloor n a \rfloor for all nn large enough. Consequently, if nn is large enough, then nma=mna\lfloor n m a \rfloor = m \lfloor n a \rfloor, so ma<mna+1m a < m \lfloor n a \rfloor + 1; that is, na<na+1/mna+1/2n a < \lfloor n a \rfloor + 1/m \le \lfloor n a \rfloor + 1/2. Hence {na}=nana<1/2\{ n a \} = n a - \lfloor n a \rfloor < 1/2, so the set {{na}:nZ+}\{ \{ n a \} : n \in \mathbb{Z}_+ \} is not dense in the closed unit interval [0,1][0, 1], and aa must be rational, say a=p/qa = p/q, where pp and qq are coprime positive integers. If q2q \ge 2, choose nn large enough such that np1(modq)n p \equiv -1 \pmod q, to reach a contradiction: 1/2>{na}={np/q}={(q1)/q}=11/q1/21/2 > \{ n a \} = \{ n p / q \} = \{ (q-1)/q \} = 1 - 1/q \ge 1/2. Consequently, q=1q = 1 and the conclusion follows.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.