IMC 2011, Day 1, Problem 3
Let be a prime number. Call a positive integer interesting if
for some polynomials and with integer coefficients.
a) Prove that the number is interesting.
b) For which is the minimal interesting number?
Eugene Goryachko and Fedor Petrov, St. Petersburg
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
(Eugene Goryachko and Fedor Petrov, St. Petersburg)
Solution. (a) Let's reformulate the property of being interesting: is interesting if is divisible by in the ring of polynomials over (the field of residues modulo ). All further congruences are modulo in this ring. We have , then , and so on by Fermat's little theorem, finally ,
(b) We write
If , then , so we have an interesting number less than . On the other hand, we show that and do satisfy the condition. First notice that by , for every fixed the greatest common divisors of interesting numbers is also an interesting number. Therefore the minimal interesting number divides all interesting numbers. In particular, the minimal interesting number is a divisor of .
For we have , so the minimal interesting number is or . But does not divide , so is not interesting. Then the minimal interesting number is .
For we have whose divisors are . The numbers and are too small and as shown above, so none of , and is interesting. So is the minimal interesting number.
Hence, is the minimal interesting number if and only if or .
Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.