Library / /54 of 136

, 1997

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Hong Kong

Let $a_n = \underbrace{677\cdots7}_{n}$ . Is it possible to find infinitely many multiples of $a_{2014}$ in the sequence $\{a_n\}$ ?

Solution

Yes. By the pigeonhole principle, two of the numbers of the form $11\cdots1$ leave the same remainder when divided by $a_{2014}$ . Their difference, which is of the form $11\cdots100\cdots0$ , is a multiple of $a_{2014}$ . Since $(a_{2014}, 10) = 1$ , we know that $a_{2014}$ divides $\underbrace{11\cdots1}_{m \text{ times}}$ for some $m \in \mathbb{Z}^+$ . It is then obvious that $a_{2014} \mid a_{2014+km}$ for any $k \in \mathbb{Z}^+$ , since
$a_{2014+km} = a_{2014} \times 10^{km} + \underbrace{77\cdots7}_{km \text{ times}}.$

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.