問題
が素数ならばは素数でないことを示せ.
出典:京都大学 2021年度 前期日程 第2次学力試験 文系 第5問
方針
がいつも5で割り切れることを狙う。ただし のときは値が5より大きい5の倍数とは直接言えないため,先に個別に合成数であることを確認する。 なら,素数 は5で割り切れないので,5で割った余りは のいずれかであり,いずれも4乗すると1になる。
解答
まず の場合を確認する。このとき であるから合成数である。
以下, とする。このとき は5で割り切れないので,5で割った余りは のいずれかである。それぞれ4乗を5で割った余りを見ると
である。したがって であり, である。
また,素数 について である。よって は5で割り切れる5より大きい整数なので,素数ではない。
別解。 の部分は,5で割った余りごとに直接確認してもよい。素数 が5の倍数でなければ, は5を法として のいずれかであり,どの場合も または であり,さらに となる。