2012年 日本数学オリンピック本選　第３問 解答例

$${p}$$を素数とする。以下の条件がすべての整数$${x}$$について成り立つような正の整数$${n}$$をすべて求めよ。
条件：$${x^n-1}$$が$${p}$$で割り切れるならば、$${p^2}$$でも割り切れる。

公益財団法人　数学オリンピック財団HP　第22回(2012年)JMO本選の問題 (imojp.org)

考え方：

すぐわかる必要条件から解を絞り、
それが十分条件でもあることを示す方針です。
目星をつけた$${n}$$について、
$${x^n-1}$$が$${p}$$で割り切れる条件を用いて
$${p^2}$$でも割り切れることを示します。
数論の基本定理を知っていることが大きな武器になります。

解答例：

$${x = p + 1}$$とすると、

$$
(p+1)^n - 1 \equiv 0   (\text{mod } p) 
$$

なので、条件を満たすには$${(p+1)^n-1}$$は$${p^2}$$で割り切れる必要がある。

$$
(p+1)^n - 1 \equiv np  (\text{mod } p^2)
$$

であるから、$${n}$$は$${p}$$の倍数でなければならない。

以下、正の整数$${a}$$を用いて$${n = ap}$$とおき、
これが常に条件を満たすことを示す。

$$
\begin{align*}
x^{ap} -1 & = (x^a)^p -1 \\
& \equiv x^a -1   (\text{mod }p)  \\
\end{align*}
$$

であるから*、$${x^{ap} -1}$$が$${p}$$の倍数の時
整数$${b}$$を用いて$${x^a = bp+1}$$と書ける。
このとき、

$$
\begin{align*}
x^{ap} -1 & = (bp +1)^p -1  \\
& \equiv 0  (\text{mod }p^2) 
\end{align*}
$$

となり、$${x^{ap} -1}$$は$${p^2}$$の倍数となる。
よって$${n=ap}$$は条件を満たす。
以上より、求める解は$${n = ap}$$ ($${a}$$は任意の正の整数。 )

コメント：

*のところでフェルマーの小定理と呼ばれる定理を使っています。
フェルマーの小定理 - Wikipedia
高校レベルでは常識とまでは言えない定理だと思いますが、
数学オリンピックの問題ではこれを知っているか否かで
かなり見通しが変わってくると思います。
求められているレベルから判断するに、
実際の答案では証明なしで用いてよいと思われます。
（証明しようとすると多少面倒ですし・・・）
ほぼ思考力勝負の数学オリンピックですが、
残念ながらこれくらいの知識（受験者レベルでは常識？）の有無で
大きく差がついてしまったりするようです。

お知らせ：

少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)