今回は次の定理を示します。1995年に京都大学で出た入試問題(1995年 京都大学 後期 文系 第4問 自分の点数を自分で決められる? | 受験の月)の内容を一般化したものとなっています。
定理
を素数、
を
より小さい正整数とする。このとき
となるは
に限られる。ただし、
は、
は
を割り切らないことを意味します。
準備
証明の前に必要となる記法や概念などを導入します。
合同式
を整数、
を2以上の整数とします。
が
が割り切れる(
を
で割ったときの余りが等しい)とき、
と
は
を法として合同であるといい、
と書きます。この合同関係は同値関係となります。
さらに、かつ
のとき
が成り立ちます。
原始根
素数に対して、ある整数
が存在して、
が互いにを法として合同でないようにすることができます(証明は省略)。このとき、
を
の原始根と言います。
言い換えると、原始根が存在するとき、
となるように、を選ぶことができるということです。
例えば、3は5の原始根です。実際
で、となります。
以上を踏まえて、証明の方に移ります。
証明
の原始根を
とすると、原始根の説明で述べた通り
が成り立つ。この両辺を乗してから
で和をとると、
である。
なので、
がわかります。
さてここからは、を場合分けして考えます。
まずのときはフェルマーの小定理により
となります。
次にのときを考える。等比級数の和の公式とフェルマーの小定理を用いると
となります。で、原始根の性質により、
です。したがって、
がわかります。
以上より、定理は証明されました。
謝辞
この記事を作成するにあたりTwitterで助言を頂きました。助言を下さった、うにさん(@unununum_1)および意識さん(@concious77)には感謝の意を申し上げます。
更新情報
のときの証明が怪しかったので直しました。(2016/03/16)
- 原始根の説明を少し変更し、証明のところを少し詳しくしました。(2016/03/17)