Track / Stage 5 / 327 of 400 #927 of 1964

Problem 927

AIME late

Number theory Difficulty 5.8 Prove it

3. Let $p_{1}, p_{2}, \cdots$ be the prime numbers in increasing order, and let $x_{0}$ be a real number between 0 and 1. For a positive integer $k$ , define
$x_{k}=\left\{\begin{array}{ll} 0, & x_{k-1}=0 ; \\ \left\{\frac{p_{k}}{x_{k-1}}\right\}, & x_{k-1} \neq 0, \end{array}\right.$

where $\{x\}$ denotes the fractional part of the real number $x$ . Find all $x_{0}\left(0<x_{0}<1\right)$ such that the sequence $x_{0}, x_{1}, \cdots$ eventually contains 0, and provide a proof.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Prompt: $x_{0}$ is a rational number.
The necessity is obvious from the definition.
Next, we prove the sufficiency.
Assume $x_{0}$ is a rational number. Then the sequence $x_{0}, x_{1}, \cdots$ is a sequence of rational numbers. Suppose there is no 0 in it.
Let $x_{k-1}=\frac{m}{n}(0<m<n,(m, n)=1)$ . Then
$x_{k}=\left\{\frac{p_{k}}{\frac{m}{n}}\right\}=\left\{\frac{n p_{k}}{m}\right\}=\frac{r}{m},$

where $0<r<m, r \equiv n p_{k}(\bmod m)$ .
Thus, the denominators of $\left\{x_{k}\right\}$ form an infinite descending sequence of positive integers, which is a contradiction.

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