「数学オリンピックチャンピオンの美しい解き方」に出てくる、整数の練習問題その5

「数学オリンピックチャンピオンの美しい解き方」に出てくる、整数の練習問題その5

問題

$p$を素数、$k$を$p$で割り切れない正の整数とする。
$1^k+2^k+3^k+\cdots +(p-1)^k$が$p$で割り切れる、または割り切れないことを示せ。

答案

帰納法。
項が一つしかない時、0は全ての数で割り切れるので成り立つ。

背理法を使う。
$1^k+2^k+3^k+\cdots +(p-1)^k=np$の時
$1^k+2^k+3^k+\cdots +p^k=n(p+1)$であればよい。
下の式から上の式の両辺を引いて
$p^k=n$
両辺に$p$を掛けると
$\begin {eqnarray}&p^{k+1}&=np\\ &&=1^k+2^k+3^k+\cdots +(p-1)^k\end{eqnarray}$
$\therefore p^{k+1}=1^k+2^k+3^k+\cdots +(p-1)^k$
これは全ての$k$において常に成り立つ式ではない。
よって題意の反証が示された。
■