IMC 2011 · Day 1 · P3

(a) Let's reformulate the property of being interesting: $n$ is interesting if $x^n - 1$ is divisible by $x^p - x + 1$ in the ring of polynomials over $\mathbb{F}_p$ (the field of residues modulo $p$). All further congruences are modulo $x^p - x + 1$ in this ring. We have $x^p \equiv x - 1$, then $x^{p^2} = (x^p)^p \equiv (x-1)^p \equiv x^p - 1 \equiv x - 2$, $x^{p^3} = (x^{p^2})^p \equiv (x-2)^p \equiv x^p - 2^p \equiv x - 2^p - 1 \equiv x - 3$ and so on by Fermat's little theorem, finally $$x^{p^p} \equiv x - p \equiv x,$$ $$x \left( x^{p^p - 1} - 1 \right) \equiv 0.$$ Since the polynomials $x^p - x + 1$ and $x$ are coprime, this implies $x^{p^p - 1} - 1 \equiv 0$.

(b) We write $$x^{1 + p + p^2 + \dots + p^{p-1}} = x \cdot x^p \cdot x^{p^2} \cdot \dots \cdot x^{p^{p-1}} \equiv x (x-1)(x-2) \dots (x - (p-1)) = x^p - x \equiv -1,$$ hence $x^{2(1 + p + p^2 + \dots + p^{p-1})} \equiv 1$ and $a = 2 (1 + p + p^2 + \dots + p^{p-1})$ is an interesting number.

If $p > 3$, then $a = \frac{2}{p-1} (p^p - 1) < p^p - 1$, so we have an interesting number less than $p^p - 1$. On the other hand, we show that $p = 2$ and $p = 3$ do satisfy the condition. First notice that by $\gcd(x^m - 1, x^k - 1) = x^{\gcd(m,k)} - 1$, for every fixed $p$ 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 $p^p - 1$.

For $p = 2$ we have $p^p - 1 = 3$, so the minimal interesting number is 1 or 3. But $x^2 - x + 1$ does not divide $x - 1$, so 1 is not interesting. Then the minimal interesting number is 3.

For $p = 3$ we have $p^p - 1 = 26$ whose divisors are $1, 2, 13, 26$. The numbers 1 and 2 are too small and $x^{13} \equiv -1 \ne +1$ as shown above, so none of 1, 2 and 13 is interesting. So 26 is the minimal interesting number.

Hence, $p^p - 1$ is the minimal interesting number if and only if $p = 2$ or $p = 3$.