2023年 日本数学オリンピック本選 第４問 解答例
正の整数$${n}$$であって、$${\frac{\phi(n)^{d(n)}+1}{n}}$$が整数であり、$${\frac{n^{\phi(n)}-1}{d(n)^5}}$$が整数でないようなものをすべて求めよ。ただし、$${n}$$と互いに素な$${1}$$以上$${n}$$以下の整数の個数を$${\phi(n)}$$で表し、$${n}$$の正の約数の個数を$${d(n)}$$で表す。
考え方：
残念ながら、整数と剰余に関する基本定理を知っているか否かでかなり見通しが変わってきます。
知っていれば$${n}$$を$${n=p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}}$$のように素因数分解し、
$${\phi(n)}$$と$${d(n)}$$の両方ともあらわに書くことができますから、
２つの式の条件について丁寧に調べていけば
$${a}$$の条件や$${k}$$の条件が順次絞り込めていきます。
必要な知識としての各定理は最後に一覧にしています。
解答例の概要：
考えてみたけど手詰まった方は、ぜひこの順番で処理できるか試してみてください。
③が難関ですが、③ができない場合は③をもとに④を示すのも練習になると思います。
①$${\phi(n)}$$と$${d(n)}$$をあらわに書き、$${\frac{\phi(n)^{d(n)}+1}{n}}$$が整数である条件から$${a_1 = a_2 = \cdots = a_k = 1}$$を示します。
②$${n}$$が偶数であるとき、$${n=2}$$のみが解であることを示します。
③$${n}$$が奇数であるとき、$${p_1-1, p_2-1, \cdots, p_k-1}$$はどれも$${2^{k+1}}$$の倍数であることを示します。
この時、フェルマーの小定理が役立ちます。
④ ③を元に、$${n}$$が奇数であるとき$${\frac{n^{\phi(n)}-1}{d(n)^5}}$$が必ず整数になることを示します。
解答例：
$${n = 1}$$は条件を満たさない。
そこで、$${k}$$を正の整数とし、
$${n}$$を素因数$${p_1, p_2, \cdots, p_k}$$を用いて
$$
n=p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}
$$
と表す。$${a_1, a_2, \cdots a_k}$$は正の整数である。
このとき、
$$
\begin{align*}
\phi(n) &= p_1^{a_1-1}p_2^{a_2-1}\cdots p_k^{a_k-1}(p_1-1)(p_2-1)\cdots (p_k -1)\\
d(n) &= (a_1 +1)(a_2 +1)\cdots (a_k +1)
\end{align*}
$$
と書ける*。
ある$${i (1\leqq i \leqq k)}$$に対して$${a_i \geqq 2}$$となるとすると、
$${\phi(n)}$$は$${p_i}$$の倍数になるため$${\phi(n)^{d(n)}+1}$$は$${p_i}$$の倍数にならず、
従って$${\frac{\phi(n)^{d(n)}+1}{n}}$$は整数になりえない。
そのため、$${a_1 = a_2 = \cdots = a_k = 1}$$が必要となる。
このとき
$$
\begin{align*}
\phi(n) &= (p_1-1)(p_2-1)\cdots (p_k -1)\\
d(n) &= 2^k
\end{align*}
$$
となる。
(i)$${n}$$が偶数のとき、
$${\frac{\phi(n)^{d(n)}+1}{n}}$$が整数になることから、
$${\phi(n)}$$が奇数であることが必要となる。
$${n}$$がさらに奇の素因数を持つと$${\phi(n)}$$は偶数となってしまうため$${n=2}$$をえる。
このとき、
$$
\begin{align*}
\frac{\phi(n)^{d(n)}+1}{n} = 1\\
\frac{n^{\phi(n)}-1}{d(n)^5} = \frac{1}{32}
\end{align*}
$$
となり条件を満たす。
よって$${n=2}$$は解である。
(ii)$${n}$$が奇数のとき、
$$
\begin{align*}
\phi(n)^{d(n)}+1 &= \{(p_1 - 1)(p_2 - 1)\cdots (p_k - 1)\}^{2^k} + 1\\
& \equiv q^{2^k} + 1 (\text{mod } p_1)\\
\end{align*}
$$
となるが、条件より$${\phi(n)^{d(n)}+1}$$が$${p_1}$$の倍数であるため、
$$
\begin{align*}
q^{2^k} &\equiv -1 (\text{mod } p_1) \tag{1}\\
q^{2^{k+1}} &\equiv 1 (\text{mod } p_1) \tag{2}
\end{align*}
$$
となる**。ただし、$${q = (p_2 - 1)\cdots (p_k - 1)}$$とおいた。
なお、$${k=1}$$とすると$${q=1}$$となるが、(1)から$${1\equiv -1 (\text{mod } p_1)}$$となり矛盾する。
よって以下$${k\geqq 2}$$とする。
ここで$${r}$$を$${q^r \equiv 1 (\text{mod }p_1)}$$となる正の整数で最小のものとし、
正の整数$${m}$$が$${q^m \equiv 1 (\text{mod }p_1)}$$となるものとする。
$${m}$$が$${r}$$の倍数でないならば、
$${0}$$以上の整数$${s}$$と$${1 \leqq t \leqq r-1}$$なる$${t}$$を用いて、
$${m = sr + t}$$とおける。
このとき、
$$
\begin{align*}
q^m &= q^{sr+t} \\
&\equiv q^t (\text{mod }p_1)\\
&\equiv 1 (\text{mod }p_1)
\end{align*}
$$
となるため、$${r}$$の最小性に反し、矛盾する。
よって$${m}$$は$${r}$$の倍数である。
これと(2)より$${r}$$は$${1, 2, 2^2, \cdots, 2^k, 2^{k+1}}$$のいずれかとなるが、
このうち$${q^{2^k} \equiv -1 (\text{mod } p_1) }$$となることから
$${r = 2^{k+1}}$$を得る。
さて、$${q^{p_1-1} \equiv 1 (\text{mod } p_1)}$$である***から、
$${p_1-1}$$は$${2^{k+1}}$$の倍数になる。
同様に、$${p_2-1, \cdots p_k-1}$$も$${2^{k+1}}$$の倍数である。
そこで、$${p_1 -1 = 2^{k+1}b_1, p_2 -1 = 2^{k+1}b_2, \cdots, p_k -1 = 2^{k+1}b_k}$$とおく。
$${b_1, b_2, \cdots, b_k}$$は正の整数である。
このとき、$${d(n)^5 = 2^{5k}}$$であり、$${\frac{n^{\phi(n)}-1}{d(n)^5}}$$が整数でないためには
$${n^{\phi(n)}-1 \not \equiv 0 (\text{mod }2^{5k}) }$$が必要になる。
$$
\begin{align*}
n^{\phi(n)}-1&= \{(2^{k+1}b_1 + 1)(2^{k+1}b_2 + 1)\cdots(2^{k+1}b_k + 1)\}^{2^{k(k+1)
}b_1b_2\cdots b_k}-1\\
&\equiv 2^{(k+1)^2}b_1b_2\cdots b_k(b_1 + b_2 + \cdots + b_k) (\text{mod } 2^{5k})
\end{align*}
$$
となるが、$${k \geqq 3}$$では$${(k+1)^2 \geqq 5k}$$となるため、
$${n^{\phi(n)}-1 \equiv 0 (\text{mod } 2^{5k})}$$となる。
$${k = 2}$$では$${b_1, b_2}$$の少なくとも一方が偶数であれば$${b_1b_2}$$が偶数であり、
両方とも奇数であれば$${b_1 + b_2}$$が偶数になるため、
$${2^{(2+1)^2}b_1b_2(b_1 + b_2) \equiv (\text{mod } 2^{10})}$$であり、
やはり$${n^{\phi(n)}-1 \equiv 0 (\text{mod } 2^{5k})}$$となる。
よって解はない。
以上より、求める解は$${n=2}$$である。
コメント：
*$${d(n)}$$ががこのように表されるのは高校数学でも基本事項かと思いますが、$${\phi(n)}$$についてはそこまで常識ではないように思います。
$${\phi(n)}$$はオイラーのφ関数やトーシェント関数と呼ばれており、
証明はネット上にたくさんあります。
オイラーのφ関数 - Wikipedia
**直接解答では使っていませんが、平方剰余の第一補充法則
（平方剰余の相互法則 - Wikipedia 内参照）
を知っていると、このあたりの処理が思い付きやすいです。
***フェルマーの小定理
フェルマーの小定理 - Wikipedia
です。数学オリンピックでは前提知識になるようです。
数学オリンピックが知識勝負になってしまうのは残念ですが、
証明も含めて高校生でも十分理解できる範囲なので、
知っておくに越したことはなさそうです。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
間違いなど見つけましたら是非お教えください。
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)