Competition problem — Number theory

Library / /31 of 136

Number theory Difficulty 7.6 National Olympiad, round 2 Prove it Hong Kong

Start with some positive integer. The following operation is performed on the number: its unit digit is split off and multiplied by $4$ , then this product is added to the remaining number. (For example, $1997$ is changed to $7 \times 4 + 199 = 227$ .) The operation is performed again and again. Prove that if the sequence of numbers obtained contains $1001$ , then none of the numbers in the sequence can be a prime number.

Solution

If the current number is $10a + b$ where $0 \le b \le 9$ , then the next number is $a + 4b$ . Note that
$10(a + 4b) = (10a + b) + 39b.$
Therefore, $13 \mid a + 4b$ if and only if $13 \mid 10a + b$ . Since $13 \mid 1001$ , all the numbers in the sequence are divisible by $13$ . The only possible prime number in this sequence is $13$ .

Now, since $1001 \rightarrow 104 \rightarrow 26 \rightarrow 26 \rightarrow \dots$ , $13$ will never appear after $1001$ . However, since $13 \rightarrow 13 \rightarrow \dots$ , it cannot appear before $1001$ as well. Thus, there is no prime in the sequence.

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.