整数論： フェルマーの小定理 その2

問題：
は素数とする。以下の条件がすべての整数について成り立つような自然数を全て求めよ。

条件：　がで割り切れるならば、でも割り切れる。

(出典：数学オリンピック　2012年　本戦　第3問)

解答：
合同式を用いると、条件は次のように書ける。

ここで、となるすべてのに関して、を満たすので、条件からを満たす必要がある。

となることから、に対して、

となり、が必要条件であることがわかる。

逆に、 (は自然数)の場合、

となる。ここでフェルマーの小定理から、を用いた。

これから、となるに対して、

であることから、

となり、すべてのに対して条件を満足する。よって求めるべきは (は自然数)である。