Maths Olympiad Prep

Library / /18 of 25

Number theory Difficulty 6.8 National olympiad Prove it Russia

Initially n>1n > 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 11, 22, 22, then on the first minute the number 12+22+221^2 + 2^2 + 2^2 appears.) Prove that the 100100th new number has at least 100100 different prime divisors.

Solution

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

Let S1,,S100S_1, \dots, S_{100} be the numbers that were written on the board in the first 100100 minutes. Suppose that before writing the number SiS_i on the board, the numbers a1,,aka_1, \dots, a_k were present. Then Si=a12+a22++ak2S_i = a_1^2 + a_2^2 + \dots + a_k^2, and the next number written is Si+1=a12+a22++ak2+Si2=Si2S_{i+1} = a_1^2 + a_2^2 + \dots + a_k^2 + S_i^2 = S_i^2.

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

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 and solution reproduced as published; topic and difficulty added by this site.