問題
を2以上の自然数とする。
(1) が素数または4のとき， は で割り切れないことを示せ。
(2) が素数でなくかつ4でもないとき， は で割り切れることを示せ。
出典：東京工業大学 2016年度 前期 理系 第4問
方針
素数の場合は， のどの因数も で割り切れないことを使う。合成数の場合は と分解し， なら2つの因数 が階乗の中に現れる。平方数の場合だけ同じ因数を2回使えないので， から とし， と を階乗の中に見つける。
解答
(1)
まず が素数であるとする。 の各因数は，いずれも で割り切れない。素数 が積を割り切るなら少なくとも1つの因数を割り切るので， は で割り切れない。
また のときは であり，これは で割り切れない。したがって (1) が示された。
(2)
は素数でないので， と書ける。ただし は自然数で， としてよい。
のとき， と は相異なる の中の数である。したがって は因数として を含むので， で割り切れる。
のとき， である。 より であり， だから である。このとき であるから， と はともに の中に現れる。よって は因数として を含み，特に で割り切れる。
以上より， が素数でなく，かつ でもないとき， は で割り切れる。