IMC 2009, Day 2, Problem 4
Let be a prime number and be the field of residues modulo . Let be the smallest set of polynomials with coefficients in such that
- the polynomials and are in , and
- for any polynomials and in the polynomial , which is the remainder of modulo , is also in .
How many polynomials are there in ?
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
Solution. Note that both of our polynomials are bijective functions on : is the cycle and is the transposition (this follows from the formula and Fermat's little theorem). So any composition formed from them is also a bijection, and reduction modulo does not change the evaluation in . Also note that the transposition and the cycle generate the symmetric group ( is the transposition , and transpositions of consecutive elements clearly generate ), so we get all permutations of the elements of .
The set only contains polynomials of degree at most . This means that two distinct elements of cannot represent the same permutation. So must contain those polynomials of degree at most which permute the elements of . By minimality, has exactly these elements.
Transcribed from the official solutions, page 3. 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.