2019年信州大学医学部で出題された整数問題です。
$n^n$ と代入すると大きな数字が出てきますが、場合分けなどは比較的オーソドックスな整数問題です。
問題
$n^n-1$ が $3$ で割り切れるような自然数 $n$ をすべて求めよ.
2019年信州大学医学部より
解答
$n$ を $3$ で割った余りで場合分けをする。
(i) $n\equiv 0 \mod 3$ のとき、$n^n-1\equiv 0^n-1\equiv -1 \mod 3$。
(ii) $n\equiv 1 \mod 3$ のとき、$n^n-1\equiv 1^n-1\equiv 0 \mod 3$。
(iii) $n\equiv -1 \mod 3$ のとき、$n^n-1\equiv (-1)^n-1\mod 3$。
ここで、$(-1)^n-1$ が $3$ で割り切れるのは、$n$ が偶数のときのみである。つまり、この $n$ は $6$ で割ると $2$ あまる数である。
(i)(ii)(iii)の結果をまとめると、$n^n-1$ が $3$ で割り切れるすべての自然数 $n$ は、$n=6k+l$ （$l=1,2,4$、$k$ は整数）の形で表される自然数である。
ワンポイント（指針の立て方）
この問題のように、実際に代入して確かめることが難しい場合は、あまりに注目します。
今回は、3で割り切れるかどうかを問われているので、3のあまりに注目するのがセオリーです。
また、(iii)において、偶奇で結果が分けられると分かったときに、6で割ったあまりに注目できるかも重要です。
