もののことわり: 整数論：　フェルマーの小定理　その2

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

条件：　 $x^n-1$ が $p$ で割り切れるならば、 $p^2$ でも割り切れる。

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

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

$x^n-1\ \equiv\ 0\ \pmod p \rightarrow x^n-1\ \equiv\ 0\ \pmod {p^2}$

ここで、 $x\ \equiv\ 1\ \pmod p$ となるすべての $x$ に関して、 $x^n-1\ \equiv\ 0\ \pmod p$ を満たすので、条件から $x^n-1\ \equiv\ 0\ \pmod {p^2}$ を満たす必要がある。

$x^n-1\ \equiv\ (x-1)(x^{n-1}+x^{n-2}+\cdots +1)\ \equiv\ 0\ \pmod {p^2}$

となることから、 $x\ \equiv\ 1\ \pmod p$ に対して、

$x^{n-1}+x^{n-2}+\cdots +1\ \equiv\ n\ \equiv 0\ \pmod p$

となり、 $n\ \equiv 0\ \pmod p$ が必要条件であることがわかる。

逆に、 $n=mp$ ( $m$ は自然数)の場合、

$x^n-1\ \equiv\ x^{mp}-1\ \equiv\ (x^m)^p-1\ \equiv\ x^m-1\ \pmod p$

となる。ここでフェルマーの小定理から、 $x^p\ \equiv\ x\ \pmod p$ を用いた。

これから、 $x^m\ \equiv\ 1\ \pmod p$ となる $x$ に対して、 $(x^m)^{p-1}+(x^m)^{p-2}+\cdots +1\ \equiv\ p\ \equiv\ 0\ \pmod p$

であることから、 $x^n-1\ \equiv\ (x^m)^p-1\ \equiv\ (x^m-1)\{(x^m)^{p-1}+(x^m)^{p-2}+\cdots +1)\ \equiv\ 0\ \pmod {p^2}$

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

もののことわり