ｐを素数，ｋをｐ−１で割り切れない正の整数とするとき，

　　１^k＋２^k＋３^k＋・・・＋（ｐ−１）^k

がｐで割り切れることを証明してみよう．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】簡単な例

　まず，簡単な例を示す．

　　１^k＋２^k＋３^k＋４^k　　（ｍｏｄ　５）

に対して，１^k，２^k，３^k，４^k　（ｍｏｄ　５）を個々に手計算し，そのあとで加算してみよう．

ｋ　　１^k　　２^k　　３^k　　４^k　　１^k＋２^k＋３^k＋４^k

０　　１　　　１　　　１　　　１　　　４

１　　１　　　２　　　３　　　４　　　０

２　　１　　　４　　　４　　　１　　　０

３　　１　　　３　　　２　　　４　　　０

４　　１　　　１　　　１　　　１　　　４

５　　１　　　２　　　３　　　４　　　０

６　　１　　　４　　　４　　　１　　　０

７　　１　　　３　　　２　　　４　　　０

８　　１　　　１　　　１　　　１　　　４

　このように１^k，２^k，３^k，４^k　（ｍｏｄ　５）はすべて周期４をもっていることがわかる．たとえば，３^k+4＝３^k・８１＝３^k　（ｍｏｄ　５）である．このことは１^k＋２^k＋３^k＋４^k　　（ｍｏｄ　５）も周期４をもっていることを意味する．ｋが４で割り切れないとき，そのときに限り

　　１^k＋２^k＋３^k＋４^k＝０　　（ｍｏｄ　５）

そうでないとき，

　　１^k＋２^k＋３^k＋４^k＝−１　　（ｍｏｄ　５）</P>

となることが予想される．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】ｍｏｄ算術</P>

　ｍｏｄ算術を扱う場合，１／２のような数はある整数と同値である．たとえば，

　　１／２＝６／２＝３　　（ｍｏｄ　５）

　　１＋１／２＋１／３＋１／４＝１＋１３＋１７＋１９＝０　　（ｍｏｄ　２５）

　また，

　　１＋１／２＋１／３＋１／４＝１＋３＋２＋４＝０　　（ｍｏｄ　５）

であるが，

　　４＝−１，３＝−２　　（ｍｏｄ　５）

を使えば，

　　１＋１／２＋１／３＋１／４＝１−２＋２−１＝０　　（ｍｏｄ　５）

同様に，

　　ｐ−１＝−１，ｐ−２＝−２，・・・　　（ｍｏｄ　ｐ）

であるから

　　１＋１／２＋１／３＋・・・＋１／（ｐ−１）＝０　　（ｍｏｄ　ｐ）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【３】証明

［Ｑ］ｋがｐ−１の倍数でない場合，

　　１^k＋２^k＋３^k＋・・・＋（ｐ−１）^k＝０　　（ｍｏｄ　ｐ）

ｋがｐ−１の倍数の場合，

　　１^k＋２^k＋３^k＋・・・＋（ｐ−１）^k＝−１　　（ｍｏｄ　ｐ）

を証明せよ．

［Ａ］ｋがｐ−１の倍数であるとき，ａ^k＝１　　（ｍｏｄ　ｐ）

　　１^k＋２^k＋３^k＋・・・＋（ｐ−１）^k＝１＋１＋１＋・・・＋１＝ｐ−１＝−１　　（ｍｏｄ　ｐ）は明らかである．

　そこで，ｋをｐ−１で割り切れないものとする．１，２，・・・，ｐ−１は順序を無視すれば，法ｐに関する原始根をｇとすると法ｐに関してｇ，２ｇ，・・・，（ｐ−１）ｇと合同である．

　　１^k＋２^k＋３^k＋・・・＋（ｐ−１）^k＝ｇ^k（１^k＋２^k＋３^k＋・・・＋（ｐ−１）^k）　　（ｍｏｄ　ｐ）

それゆえ

　　１^k＋２^k＋３^k＋・・・＋（ｐ−１）^k＝０　　（ｍｏｄ　ｐ）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝