JMO 2023
問題 4

$n$ が素数のとき条件を満たすのは $n=2$ のみである．以下では $n$ は合成数とする．$n\mid \phi(n)^{d(n)}+1$ より $n$ は平方因子を持たない．このとき $2$ 以上の整数 $k$ と $k$ 個の素数 $p_1,\dots,p_k$ を用いて

$$n=p_1p_2\cdots p_k$$

と表すことができ，$n\mid \phi(n)^{d(n)}+1$ は

$$p_i\mid \phi(n)^{2^k}+1\quad (i=1,2,\dots,k)$$

が必要である．よって $\text{mod} ~ p_i$ における $\phi(n)$ の位数は $2^{k+1}$ なので

$$2^{k+1}\mid p_i-1$$

が成り立つ．よって $n^2-1$ は $2$ で $k+2$ 回割り切れる．以上より，LTEの補題と $2^{5k}\nmid n^{\phi(n)}-1$ より

$$5k-1\geq v_2(n^{\phi(n)}-1)=v_2(n^2-1)-1+v_2(\phi(n))\geq k+1+k(k+1)$$

が成り立つ．この不等式を満たすものは $k=2$ のみである．よって整数 $a,b$ を用いて $p_1=8a+1,p_2=8b+1$ と表せるが，$a,b$ の偶奇に関わらず

$$9\geq v_2(n+1)+v_2(n-1)-1+v_2(8a\cdot 8b)=9+v_2(a+b+8)+v_2(ab)\geq 10$$

が成り立つので矛盾する．

以上より条件を満たす $n$ は $2$ のみである．