Initially 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 , , , then on the first minute the number appears.) Prove that the th new number has at least different prime divisors.
Solution
Let be the number appearing on the board on the th minute. Then , so contains all prime divisors of plus at least one more.
Let be the numbers that were written on the board in the first minutes. Suppose that before writing the number on the board, the numbers were present. Then , and the next number written is .
Thus, . Therefore, contains in its prime factorization all the prime numbers that divide , plus at least one new prime divisor (a divisor of ). Since , contains at least one prime divisor in its factorization. Hence, by induction, for , the number contains at least 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.