ねしゃ～のブログ

数学オリンピック本選2023 第4問

前提知識

$p=2$ 版のLTEの補題として以下が成り立つ(証明はLTEの補題とその応用～一般化へ向けて～ | Mathlogの定理3とかを参考にするといいです)

$n$ が偶数かつ $v_2(x)=v_2(y)=0$ のとき

$v_2(x^n-y^n)=v_2(x^2-y^2)+v_2(n)-1$

特に $y=1$ なら

$v_2(x^n-1)=v_2(x+1)+v_2(x-1)+v_2(n)-1\geq v_2(x-1)+v_2(n)$

LTEの補題を使わずに

$n=b\cdot 2^a (a=v_2(n))$ とおいて

$x^n-1=(x^{b\cdot 2^{a-1}}+1)(x^{b\cdot 2^{a-2}}+1)\cdots (x^{b}+1)(x-1)(x^{b-1}+x^{b-2}\cdots +1)$

を用いて直接求めてもよい

解法

$n=p_1^{e_1} \dots p_k^{e_k}$ ( $p_i$ は互いに異なる素数)とおくと

$d(n)=(e_1+1)\dots (e_k+1)$

$\phi (n)=p_1^{e_1-1} \dots p_k^{e_k-1} (p_1-1)\dots (p_k-1)$

よって $e_i\gt 1$ となるような $i$ があった場合 $\phi (n)$ が $p_i$ で割り切れるので $\phi (n)^{d(n)}+1$ が $p_i$ で割り切れず1つ目の条件に矛盾

したがって整理すると

$n=p_1 \dots p_k$

$d(n)=2^k$

$\phi (n)=(p_1-1)\dots (p_k-1)$

と表せる

$p_i$ に偶素数と奇素数がともに含まれていた場合 $\phi (n)^{d(n)}+1$ は奇数で $n$ は偶数になるので矛盾

偶素数のみの場合は $n=2$ しかありえずこれは条件を満たす

また $n=1$ は条件を満たさない

以下 $p_i$ は全て奇素数で $k\geq 1$ とする

1つ目の条件は $\phi(n)^{2^k}\equiv -1\pmod n$ と書け、中国剰余定理より任意の $i$ において、

$\phi(n)^{2^k}\equiv -1\pmod {p_i}$

$a$ を $p_i$ の原始根とし $a^m \equiv \phi(n)\pmod {p_i}(m\lt p_i-1)$ だとすると $a^{m\cdot 2^k}\equiv -1\pmod {p_i}$ だから

$(p_i-1)/2\mid m\cdot 2^k$ かつ $p_i-1\nmid m\cdot 2^k$ *1

したがって $v_2(p_i-1)=v_2(m\cdot 2^k)+1=v_2(m)+k+1\geq k+1\cdots (1)$

2つ目の条件に着目する

$\phi(n)$ が偶数かつ $n$ は奇数だから $p=2$ 版のLTEの補題を使うと

$v_2(n^{\phi(n)}-1)\geq v_2(n-1)+v_2(\phi(n))\cdots (2)$

$(1)$ より任意の $i$ において $p_i\equiv 1\pmod{2^{k+1}}$ なので、 $n\equiv 1\pmod{2^{k+1}}$ となり

$v_2(n-1)\geq k+1\cdots (3)$

また $\phi (n)=(p_1-1)\dots (p_k-1)$ 及び $(1)$ より

$v_2(\phi(n))\geq k(k+1)\cdots (4)$

よって $(2),(3),(4)$ より $v_2(n^{\phi(n)}-1)\geq (k+1)^2$

ここで $v_2(d(n)^5)=v_2(2^{5k})=5k$ だから

2つ目の条件より $(k+1)^2\lt 5k$

したがって $k=1,2$

・ $k=1$ の場合

$(\phi(n)^{d(n)}+1)/n=( (p_1-1)^2+1)/p_1=p_1-2+2/p_1$ より整数とならないので矛盾

・ $k=2$ の場合

$v_2(p_i-1)\geq k+1=3$ が成り立つ

ここで $v_2(p_1-1)=v_2(p_2-1)=3$ を仮定すると

$n=p_1 p_2$ だから $v_2(n-1)\geq 4$ より $(2),(4)$ と併せて

$v_2(n^{\phi(n)}-1)\geq 10=v_2(d(n)^5)$ より矛盾

一般性を失わずに $v_2(p_1-1)\geq 4$ とする

$v_2(\phi (n))=v_2( (p_1-1)(p_2-1))=v_2(p_1-1)+v_2(p_2-1)\geq 7$ だから $(2),(3)$ と併せて

$v_2(n^{\phi(n)}-1)\geq 10=v_2(d(n)^5)$ より矛盾

したがって条件を満たすのは $n=2$ のみである

*1: $(ℤ/p_iℤ)^×$ は位数 $p_i-1$ の巡回群であり、 $a^{(p_i-1)/2}\equiv -1$ になることを利用している