1からp-1までのn乗和、ただしpは素数

今回は次の定理を示します。1995年に京都大学で出た入試問題（1995年京都大学後期文系第4問自分の点数を自分で決められる？ | 受験の月）の内容を一般化したものとなっています。

定理

$p$ を素数、 $n$ を $p$ より小さい正整数とする。このとき
$p \nmid 1^n + 2^n + \dots + (p-1)^n$
となる $n$ は $n=p-1$ に限られる。ただし、 $a \nmid b$ は、 $a$ は $b$ を割り切らないことを意味します。

準備

証明の前に必要となる記法や概念などを導入します。

合同式

$a,b$ を整数、 $m$ を2以上の整数とします。 $a-b$ が $m$ が割り切れる（ $a,b$ を $m$ で割ったときの余りが等しい）とき、 $a$ と $b$ は $m$ を法として合同であるといい、
$a \equiv b \pmod{m}$
と書きます。この合同関係は同値関係となります。

さらに、 $a \equiv b \pmod{m}$ かつ $c \equiv d \pmod{m}$ のとき

$a + c \equiv b + d \pmod{m}$
$ac \equiv bd \pmod{m}$

が成り立ちます。

後でフェルマーの小定理というものを使います。これは、 $a$ を素数 $p$ と互いに素な整数とするとき
$a^{p-1} \equiv 1 \pmod{p}$
が成り立つという定理です。

原始根

素数 $p$ に対して、ある整数 $r\:(0 < r < p)$ が存在して、
$1,r,r^2,\dots,r^{p-2}$
が互いに $p$ を法として合同でないようにすることができます（証明は省略）。このとき、 $r$ を $p$ の原始根と言います。

言い換えると、原始根 $r$ が存在するとき、
$\{ 0, \dots, p-2 \} = \{ k_0, \dots, k_{p-2} \}$
$r^{k_j} \equiv j+1 \pmod{p}$
となるように、 $k_0, \dots, k_{p-2}$ を選ぶことができるということです。

例えば、3は5の原始根です。実際
$3^0 \equiv 1 \pmod{5}$
$3^1 \equiv 3 \pmod{5}$
$3^2 \equiv 4 \pmod{5}$
$3^3 \equiv 2 \pmod{5}$
で、 $k_0=0, k_1=3, k_2=1, k_3=2$ となります。

以上を踏まえて、証明の方に移ります。

証明

$p$ の原始根を $r$ とすると、原始根の説明で述べた通り
$r^{k_j} \equiv j+1 \pmod{p}$
が成り立つ。この両辺を $n$ 乗してから $j=0, \dots, p-2$ で和をとると、
$\displaystyle \sum_{j=0}^{p-2} r^{k_j n} \equiv \sum_{j=0}^{p-2} (j+1)^n \pmod{p}$
である。

$\displaystyle \sum_{j=0}^{p-2} r^{k_j n} = 1 + r^n + (r^2)^n + \dots + (r^{p-2})^n,$
$\displaystyle \sum_{j=0}^{p-2} (j+1)^n = 1^n + 2^n + \dots + (p-1)^n$
なので、
$\begin{align} & 1^n + 2^n + \dots + (p-1)^n \\ & \equiv 1 + r^n + (r^2)^n + \dots + (r^{p-2})^n \pmod{m} \\ & \equiv 1 + r^n + (r^n)^2 + \dots + (r^n)^{p-2} \pmod{m} \end{align}$
がわかります。

さてここからは、 $n$ を場合分けして考えます。
まず $n=p-1$ のときはフェルマーの小定理により
$\begin{align} & 1 + r^n + (r^n)^2 + \dots + (r^n)^{p-2}\\ & \equiv 1 + 1 + 1^2 + \dots + 1^{p-2} \pmod{p} \\ & \equiv p-1 \pmod{p} \end{align}$
となります。

次に $n< p-1$ のときを考える。等比級数の和の公式とフェルマーの小定理を用いると
$\begin{align} & ( r^n - 1 ) ( 1 + r^n + (r^n)^2 + \dots + (r^n)^{p-2} ) \\ & = r^{n( p-1 )} - 1\\ & \equiv 0 \pmod{p} \end{align}$
となります。 $n< p-1$ で、原始根の性質により、
$r^n - 1 \not \equiv 0 \pmod{p}$
です。したがって、
$1 + r^n + (r^n)^2 + \dots + (r^n)^{p-2} \equiv 0 \pmod{p}$
がわかります。