読者です 読者をやめる 読者になる 読者になる

プログラミングする数学信者

数学信者が数学とプログラミングの話題を中心にして何か書きます

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

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

定理

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

準備

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

合同式

a,bを整数、mを2以上の整数とします。a-bmが割り切れる(a,bmで割ったときの余りが等しい)とき、abmを法として合同であるといい、
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を法として合同でないようにすることができます(証明は省略)。このとき、rpの原始根と言います。

言い換えると、原始根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}
がわかります。

以上より、定理は証明されました。

謝辞

この記事を作成するにあたりTwitterで助言を頂きました。助言を下さった、うにさん(@unununum_1)および意識さん(@concious77)には感謝の意を申し上げます。

更新情報

  • n< p-1 のときの証明が怪しかったので直しました。(2016/03/16)
  • 原始根の説明を少し変更し、証明のところを少し詳しくしました。(2016/03/17)