2012年 日本数学オリンピック本選 第３問 解答例
$${p}$$を素数とする。以下の条件がすべての整数$${x}$$について成り立つような正の整数$${n}$$をすべて求めよ。
条件：$${x^n-1}$$が$${p}$$で割り切れるならば、$${p^2}$$でも割り切れる。
考え方：
すぐわかる必要条件から解を絞り、
それが十分条件でもあることを示す方針です。
目星をつけた$${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)