Problem

Source: SRMC 2007

Tags: number theory, prime numbers



On the board are written $2 , 3 , 5 ,... , 2003$ , that is, all the prime numbers of the interval $[2,2007]$ . The operation of simplification is the replacement of two numbers $a , b$ by a maximal prime number not exceeding $\sqrt{a^2-a b+b^2}$ . First, the student erases the number $q, 2<q<2003$, then applies the simplification operation to the remaining numbers until one number remains. Find the maximum possible and minimum possible values of the number obtained in the end. How do these values depend on the number $q$?