Track / Stage 6 / 343 of 400 #1823 of 2444

Problem 1823

National Olympiad, first round

Number theory Difficulty 6.8 Prove it Russian Mathematical Olympiad · Russia

Initially $n > 1$ positive integers are written on the board. On each minute, a new number that is the sum of squares of all already written numbers appears on the board. (For example, if initial numbers were $1$ , $2$ , $2$ , then on the first minute the number $1^2 + 2^2 + 2^2$ appears.) Prove that the $100$ th new number has at least $100$ different prime divisors.

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

Let $S_i$ be the number appearing on the board on the $i$ th minute. Then $S_{i+1} = S_i(S_i + 1)$ , so $S_{i+1}$ contains all prime divisors of $S_i$ plus at least one more.

Let $S_1, \dots, S_{100}$ be the numbers that were written on the board in the first $100$ minutes. Suppose that before writing the number $S_i$ on the board, the numbers $a_1, \dots, a_k$ were present. Then $S_i = a_1^2 + a_2^2 + \dots + a_k^2$ , and the next number written is $S_{i+1} = a_1^2 + a_2^2 + \dots + a_k^2 + S_i^2 = S_i^2$ .

Thus, $S_{i+1} = S_i(S_i + 1)$ . Therefore, $S_{i+1}$ contains in its prime factorization all the prime numbers that divide $S_i$ , plus at least one new prime divisor (a divisor of $1 + S_i$ ). Since $S_1 > 1$ , $S_1$ contains at least one prime divisor in its factorization. Hence, by induction, for $i = 1, 2, \dots, 100$ , the number $S_i$ contains at least $i$ distinct prime divisors in its factorization.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.