Let $p$ be a prime satisfying $p^2\mid 2^{p-1}-1$, and let $n$ be a positive integer. Define \[ f(x) = \frac{(x-1)^{p^n}-(x^{p^n}-1)}{p(x-1)}. \] Find the largest positive integer $N$ such that there exist polynomials $g(x)$, $h(x)$ with integer coefficients and an integer $r$ satisfying $f(x) = (x-r)^N g(x) + p \cdot h(x)$. Proposed by Victor Wang
Problem
Source: ELMO 2014 Shortlist N11, by Victor Wang
Tags: algebra, polynomial, modular arithmetic, number theory proposed, number theory
26.07.2014 15:14
Using Kummer's theorem and Lucas' theorem, one can show that \[(x-1)^{p^n} - (x^{p^n} -1) = \sum_{k=1}^{p^n-1} (-1)^{k+1} x^k \binom{p^n}{k} \\ \equiv \sum_{k=1}^{p-1} (-1)^{k+1} x^{p^{n-1} k} \binom{p}{k} \\ = (x^{p^{n-1}} -1)^p - (x^{p^n}-1) \pmod{p^2}. \] Now let $x^{p^{n-1}}=X$. Then $\frac{(x-1)^{p^n} - (x^{p^n}-1)}{p} \equiv \frac{(X-1)^p - (X^p -1)}{p} \bmod{p}$. Let $g(X) = \frac{(X-1)^p - (X^p -1)}{p}$. Since $g^{\prime\prime}(X) = (p-1)((X-1)^{p-2} - X^{p-2})$ has no solutions modulo $p$, every root of $g(X)$ must have a multiplicity at most $2$. By the condition that $p$ is a Wieferich prime, $g(2) \equiv 0$ and $g^\prime (2) = (2-1)^{p-1} - 2^{p-1} \equiv 0$, and hence $(X-2)^2$ is a factor of $g(X)$. Now let $g(X)= (X-a_1) \cdots (X-a_m) R(X)$ where $R$ has no roots modulo $p$. Then \[f(x) = (x^{p^{n-1}}-a_1) \cdots (x^{p^{n-1}} - a_m) R(x^{p^{n-1}})/(x-1) \\ \equiv (x-a_1)^{p^{n-1}} \cdots (x-a_m)^{p^{n-1}} R(x^{p^{n-1}}) /(x-1) \pmod{p}. \] Since $x^{p^{n-1}} \equiv x \pmod{p}$ for all $x$, the new polynomial $R(x^{p^{n-1}})$ will have no roots also. Therefore the largest $N$ is $2 p^{n-1}$ which is obtained at $r=2$(or more).
26.07.2014 19:28
Yes, the identity is something I found while working on this: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=489734 (see the MathOverflow post for details) A slightly different way to think about this after the $(x^{p^{n-1}}-1)^p$ simplification (done in the first official solution) is $f(x) = g(x^{p^{n-1}}) = g(x)^{p^{n-1}}$ in $\mathbb{F}_p$, by the Frobenius automorphism in the second step. In fact, $g(x) = -(x/1 + \cdots + x^{p-1}/(p-1))$, so $g'(x) = -(1+x+\cdots+x^{p-2}) = -\frac{x^{p-1}-1}{x-1} = -(x-2)(x-3)\cdots(x-(p-1))$, which makes it immediately obvious that there are no roots of multiplicity greater than $2$.