(x+1)^n - x^n mod pが全射になるnの特定

これは 第17回近大数学コンテスト(2014)の最終問 であり、解けなかったので検索などすると Q&A に行き当たり、 そこで紹介されていた論文
のSection 4に証明があった。文脈としては射影平面に関する性質を示すための補題的な位置づけのようだった。（なるほどそういうところからコンテストの題材を見つけてくるのかなどと感心した。）

さて、$n=2$のときは$f(x)$は線形で明らかに全単射である。また、$x^n$は周期$p-1$を持つので、$n \equiv 2 \pmod{p-1} $のときも全単射であることはすぐにわかる。それ以外のときに決して全単射にならないことを示すのが難しかった。

$x^n$は周期$p-1$を持つため、$n=1$と$3\le n \le p-1$の場合を調べればよい。$n=1$の場合は恒等的に$f(x)=1$で全射でないため、残り$3\le n \le p-1$を考える。

以下の内容は上記の論文に書かれた証明を自分の言葉で整理したものになる。
$k = \left\lfloor\frac{p-1}{n}\right\rfloor$
とおく。つまり、
$kn \le p-1,\quad (k+1)n > p-1$
を満たす整数$k$を取る。

最近の別ノート でも登場した以下の性質を所々で利用する：

$kn\le p-1$の等号が成立するかどうかで証明の有効性が変わるので場合分けする。

場合1：$kn = p-1$の場合
この場合、$n$個の$k$次剰余が
$z^n \equiv 1 \pmod{p}$
を満たすことになる。特に$3\le n\le p-1$であるから、$z^n \equiv 1$を満たす$z$が$z\equiv 1$以外に少なくとも2個存在する。$z^n\equiv 1$を満たす$z\not\equiv 1$に対して、$z-1$の逆元を$x$とおくと、$(x+1)^n \equiv x^n \pmod{p}$,すなわち$f(x)\equiv 0$が成り立つ。したがってそのような$z$が2個以上存在することから$f$は全射でない。

場合2：$kn \ne p-1$、すなわち$kn < p-1$
この場合、次の和を考える：
$ S = \sum_{x=0}^{p-1} f(x)^{2k}. $
$3\le n \le p-1$より$0<2k< p-1$であるから、もし$f(x)$が全単射であれば、この和は命題1の(B)に該当し、$0 \bmod p$になるはずである。従って$S\not\equiv 0 \pmod{p}$を示せば良い。

二項展開して、
$S = \sum_{a=0}^{2k}\sum_{x=0}^{p-1}\binom{2k}{a}(-1)^a (x+1)^{(2k-a)n}x^{an} $
と表す。以下に$a=k$だけが寄与してそれが非零であることを示す。

パート1：$a\ge k+1$

$(x+1)^{(2k-a)n} x^{an}$ を$x$の多項式として展開した結果を考える。$k$の定義より $p-1 < an$ であるから、現れる最低次数は$(p-1)$次より大きい。一方最高次数は$2kn$で、これは場合分け条件より$2(p-1)$より小さい。従って展開したすべての項は命題1の(B)に該当し、$x$に関する和$\bmod p$は$0$となる。

パート2：$a\le k-1$

$y=x+1$と変数変換すると、パート1と同様に和が0と分かる。

パート3：$a=k$
$(x+1)^{kn}x^{kn}$の展開結果を考える。$kn\le p-1$なので二項係数に$p$の倍数が現れない。よって展開結果は$x^{kn}$から$x^{2kn}$までの全ての次数でmod $p$で非零な項を持つ。$k$の定義によりこの次数範囲は$x^{p-1}$を含み、場合分け条件より$x^{2(p-1)}$には至らない。よって命題1(A)より$x$に関する和$\bmod p$は非零である。

以上より、$S\not\equiv 0\pmod{p}$が示され、従って$f(x)$は全単射でないことが示された。