Zsigmondyの定理(Zsigmondy's theorem)とは、互いに素な整数 $a>b\ge1$ と $n\ge2$ について、$a^n-b^n$ が、$k< n$ のどの $a^k-b^k$ も割らない素因数(原始素因数)を持つという定理で、例外は $n=2$ で $a+b$ が $2$ の冪の場合と $(a,b,n)=(2,1,6)$ の場合だけである。原始素因数は円分多項式の値 $\Phi_n(a,b)$ の素因数のうち $n$ を割らないものであり、$n\ge3$ では原始でない素因数は $n$ の最大の素因数に限られ 1 乗でしか現れないので、$\Phi_n(a,b)$ の下からの評価と比べて定理が証明される。系として $a^n+b^n$ の場合(例外は $2^3+1$)や、$n$ を法として $1$ に合同な素数の無限性が得られる。
前提知識: 円分多項式, 有限体, Fermatの小定理
Zsigmondyの定理(Zsigmondy's theorem)は、$a^n-b^n$ という形の数が、それより小さい指数の $a^k-b^k$ には現れない新しい素因数をほとんどいつでも持つことを述べる定理である。たとえば $2^n-1$ を並べると $3,7,15,31,63,127,255,\dots$ となり、$2^4-1=15$ の素因数 $5$、$2^8-1=255$ の素因数 $17$ はそれ以前の項には現れない。ところが $2^6-1=63=3^2\cdot7$ の素因数 $3$ と $7$ はすでに $2^2-1$ と $2^3-1$ に現れている。Zsigmondy の定理は、互いに素な整数 $a>b\ge1$ と $n\ge3$ についてこの現象が起きるのは $(a,b,n)=(2,1,6)$ だけであることを主張する。
このような「新しい素因数」を 原始素因数 という。原始素因数 $p$ は、法 $p$ で $a/b$ の位数がちょうど $n$ になる素数のことであり、$p\equiv1\pmod n$ を満たす。$a$ が素数の冪 $q$、$b=1$ のときは、有限体 $\mathbb F_{q^n}$ の乗法群の中で、どの真の部分体にも入らない素数位数の元を与える。$b=1$ の場合は Bang が 1886 年に(Tidsskrift for Mathematik 誌)、一般の場合は Zsigmondy が 1892 年に(Zsi92)示した。Birkhoff と Vandiver も 1904 年に同じ主題の論文(BV04)を書いている(以上の経緯は Dic19 p. 195、pp. 385–386、p. 388 による)。
この記事では、原始素因数を 円分多項式 の値の素因数として捉え直し、「原始でない素因数は $n$ の最大の素因数だけで、しかも 1 乗でしか現れない」こと(lem-zsig-nonprimitive)と、円分多項式の値の下からの評価(lem-zsig-lower)を組み合わせて、主定理(thm-zsig-main)を完全に証明する。系として $a^n+b^n$ の場合と、$n$ を法として $1$ に合同な素数の無限性を導く。
以下、$a>b\ge1$ は互いに素な整数とする。
$n\ge1$ とする。素数 $p$ が $a^n-b^n$ を割り切り、$1\le k< n$ のどの $k$ についても $a^k-b^k$ を割り切らないとき、$p$ を $a^n-b^n$ の 原始素因数(primitive prime divisor)という。
$n=1$ では条件は「$p\mid a-b$」だけなので、$a-b>1$ なら原始素因数がある。以下では $n\ge2$ を考える。
$a>b\ge1$ を互いに素な整数、$n\ge2$ とする。$a^n-b^n$ は原始素因数を持つ。ただし次の場合を除く。
証明は節「主定理の証明」の prf-zsig-main で行う。原始素因数を円分多項式の値 $\Phi_n(a,b)$ の素因数として捉え(lem-zsig-cyclo)、$n\ge3$ では原始でない素因数が $n$ の最大の素因数 $P(n)$ だけで、しかも 1 乗でしか現れないこと(lem-zsig-nonprimitive)と、$\Phi_n(a,b)>P(n)$(lem-zsig-lower)を比べる。
除外の 1 は、たとえば $(a,b)=(3,1)$ で $3^2-1=8$ の素因数 $2$ がすでに $3-1=2$ を割ることにあたる。2 は冒頭の $2^6-1=63$ である。Dickson の記述では、Zsigmondy はこの 2 つの除外のほかに、$n=1$、$a-b=1$ の場合と、$a,b$ の符号も許したときの $n=3$、$a=\pm2$、$b=\mp1$($2^3+1$ にあたる)を例外に挙げている(Dic19 p. 195)。
$a=2$、$b=1$ で $n=2,\dots,12$ を並べる。$\Phi_n(2,1)$ は後で定める同次の円分多項式の値である。
| $n$ | $2^n-1$ | 原始素因数 | $\Phi_n(2,1)$ |
|---|---|---|---|
| $2$ | $3$ | $3$ | $3$ |
| $3$ | $7$ | $7$ | $7$ |
| $4$ | $3\cdot5$ | $5$ | $5$ |
| $5$ | $31$ | $31$ | $31$ |
| $6$ | $3^2\cdot7$ | なし | $3$ |
| $7$ | $127$ | $127$ | $127$ |
| $8$ | $3\cdot5\cdot17$ | $17$ | $17$ |
| $9$ | $7\cdot73$ | $73$ | $73$ |
| $10$ | $3\cdot11\cdot31$ | $11$ | $11$ |
| $11$ | $23\cdot89$ | $23,\ 89$ | $2047$ |
| $12$ | $3^2\cdot5\cdot7\cdot13$ | $13$ | $13$ |
どの行でも、原始素因数は $n$ を法として $1$ に合同である($11\equiv1\pmod{10}$、$23\equiv89\equiv1\pmod{11}$ など)。$n=6$ の行だけ $\Phi_6(2,1)=3$ が $n$ の最大の素因数 $3$ に等しく、原始素因数がない。$n$ が素数のときの $2^n-1$ は Mersenne素数 の候補である。
素数 $p$ が $a^n-b^n$ を割り切るとする。
1.$p\mid b$ なら $p\mid a^n$ から $p\mid a$ となり、$\gcd(a,b)=1$ に反する。$p\mid a$ も同様である。
2.$p\nmid b$ なので、$p\mid a^k-b^k$ は $\mathbb F_p$ で $(ab^{-1})^k=1$、すなわち $c^k=1$ と同値であり、これは $e\mid k$ と同値である。
3.2 により、$p\mid a^k-b^k$ となる最小の $k\ge1$ が $e$ である。$p\mid a^n-b^n$ なので $e\mid n$ であり、原始素因数であることは「$k< n$ では割らない」こと、すなわち $e=n$ と同値である。Fermatの小定理 により $c^{p-1}=1$ なので $e\mid p-1$ である。$\square$
$n$ 次の 円分多項式 $\Phi_n(x)=\prod_\zeta(x-\zeta)$($\zeta$ は原始 $n$ 乗根を動く)は次数 $\varphi(n)$ の整数係数のモニック多項式で、$x^n-1=\prod_{d\mid n}\Phi_d(x)$ を満たす(円分多項式 の定義「円分多項式」)。その同次化を
$$
\Phi_n(x,y):=y^{\varphi(n)}\Phi_n(x/y)=\prod_\zeta(x-\zeta y)
$$
とおく。$\Phi_n(x,y)$ は整数係数の同次多項式で、$x^n-y^n=\prod_{d\mid n}\Phi_d(x,y)$ が成り立つ($x^n-1$ の分解に $x/y$ を代入して $y^n=\prod_{d\mid n}y^{\varphi(d)}$ を掛ける)。
$n\ge2$ とする。
1.$\Phi_n(a,b)$ は整数である。$\zeta$ と $\bar\zeta$ は組になるので、$\Phi_n(a,b)=\prod_\zeta\lvert a-\zeta b\rvert$ は正の実数である($n\ge3$ では $\zeta\ne\bar\zeta$ の組の積 $\lvert a-\zeta b\rvert^2$、$n=2$ では $a+b$)。
2.$a^n-b^n=\prod_{d'\mid n}\Phi_{d'}(a,b)$、$a^d-b^d=\prod_{d'\mid d}\Phi_{d'}(a,b)$ で、各因子は正の整数である。商は $\prod_{d'\mid n,\ d'\nmid d}\Phi_{d'}(a,b)$ であり、$n\nmid d$ なので $\Phi_n(a,b)$ を因子に含む。
3.$p$ を原始素因数とする。$p\mid a^n-b^n=\prod_{d\mid n}\Phi_d(a,b)$ で、$d< n$ の $\Phi_d(a,b)$ は $a^d-b^d$ を割るので $p$ で割れない。よって $p\mid\Phi_n(a,b)$ である。逆に $p\mid\Phi_n(a,b)$、$p\nmid n$ とする。$p\mid a^n-b^n$ なので lem-zsig-order の $c$ が定まり、$a\equiv cb\pmod p$ から $0\equiv\Phi_n(a,b)\equiv b^{\varphi(n)}\Phi_n(c)\pmod p$、すなわち $c$ は $\mathbb F_p$ で $\bar\Phi_n$ の根である。円分多項式 の定理「有限体上の円分多項式の分解」の 1 により、$\bar\Phi_n$ の根は位数 $n$ の元なので $e=n$ であり、lem-zsig-order の 3 により $p$ は原始素因数である。$\square$
3 から、原始素因数の積は $\Phi_n(a,b)$ から $n$ を割る素因数を取り除いた部分になる。次の補題は、取り除かれる部分がごく小さいことを示す。$n\ge2$ の最大の素因数を $P(n)$ と書く。
$n\ge2$ とし、素数 $p$ が $\Phi_n(a,b)$ を割り切るが $a^n-b^n$ の原始素因数でないとする。lem-zsig-order の位数を $e$ とする。
まず次の事実を使う。整数 $A,B$ で $A\equiv B\pmod p$、$p\nmid B$ なら、$m\ge1$ について
$$
\frac{A^m-B^m}{A-B}=\sum_{i=0}^{m-1}A^{m-1-i}B^i\equiv mB^{m-1}\pmod p\qquad(*)
$$
である(各項が $B^{m-1}$ に合同)。
1.$p\mid a^n-b^n$ なので $e\mid n$ であり、原始でないので $e< n$ である。$n=em$ と書き、$A:=a^e$、$B:=b^e$ とおくと $p\mid A-B$(lem-zsig-order の 2)で $p\nmid B$ である。lem-zsig-cyclo の 2($d=e$)により $p$ は $(a^n-b^n)/(a^e-b^e)=(A^m-B^m)/(A-B)$ を割り、$(*)$ によりこれは $mB^{m-1}$ に合同なので $p\mid m$ である。
$m=p^km'$($k\ge1$、$p\nmid m'$)とし、$m'>1$ と仮定する。$n_1:=ep^k$ は $n$ の約数で $n_1< n$ であり、$e\mid n_1$ なので $p\mid a^{n_1}-b^{n_1}$ である。$A_1:=a^{n_1}$、$B_1:=b^{n_1}$ に $(*)$ を使うと、$(a^n-b^n)/(a^{n_1}-b^{n_1})\equiv m'B_1^{m'-1}\not\equiv0\pmod p$ である。ところが lem-zsig-cyclo の 2 により $\Phi_n(a,b)$ はこの商を割り、$p\mid\Phi_n(a,b)$ なので矛盾する。よって $m'=1$、$n=ep^k$ である。
lem-zsig-order の 3 の証明のとおり $e\mid p-1$ なので、$e$ の素因数はすべて $p$ より小さい。よって $p$ は $n=ep^k$ の最大の素因数である。
2.$p$ が奇数の場合。$A:=a^{n/p}$、$B:=b^{n/p}$ とおく。$k\ge1$ なので $e\mid n/p$ であり、$A=B+t$、$p\mid t$ と書ける。$0\le j< p$ について $A^j=(B+t)^j\equiv B^j+jB^{j-1}t\pmod{p^2}$ なので
$$
\frac{A^p-B^p}{A-B}=\sum_{i=0}^{p-1}A^{p-1-i}B^i\equiv pB^{p-1}+tB^{p-2}\sum_{i=0}^{p-1}(p-1-i)=pB^{p-1}+tB^{p-2}\frac{p(p-1)}2\pmod{p^2}
$$
である。$p$ は奇数なので $\frac{p(p-1)}2$ は $p$ の倍数で、$p\mid t$ から最後の項は $p^2$ で割れる。よって左辺は $pB^{p-1}$ と法 $p^2$ で合同で、$p\nmid B$ からちょうど 1 回だけ $p$ で割れる。lem-zsig-cyclo の 2($d=n/p$)により $\Phi_n(a,b)$ はこの商を割るので、$p^2\nmid\Phi_n(a,b)$ である。
$p=2$ の場合。$e\mid p-1=1$ なので $e=1$、$n=2^k$ で、$n\ge3$ から $k\ge2$ である。$\Phi_{2^k}(x)=x^{2^{k-1}}+1$(円分多項式 の例「Fermat 数と円分多項式」)なので $\Phi_n(a,b)=a^{2^{k-1}}+b^{2^{k-1}}$ である。$2\mid a-b$ と $\gcd(a,b)=1$ から $a,b$ はともに奇数で、$2^{k-1}$ は偶数なので $a^{2^{k-1}}\equiv b^{2^{k-1}}\equiv1\pmod 4$ である。よって $\Phi_n(a,b)\equiv2\pmod4$ で、$4\nmid\Phi_n(a,b)$ である。$\square$
2 で $n\ge3$ は外せない。$n=2$ では $\Phi_2(a,b)=a+b$ で、$(a,b)=(7,1)$ なら $a+b=8=2^3$ である。
まとめると、$n\ge3$ のとき
$$
\Phi_n(a,b)=N\cdot P(n)^{\varepsilon},\qquad\varepsilon\in\{0,1\}
$$
と書け、$N$ の素因数はすべて $a^n-b^n$ の原始素因数である。したがって $a^n-b^n$ が原始素因数を持たないなら $\Phi_n(a,b)\in\{1,P(n)\}$ となる。
$n\ge3$ とする。$(a,b,n)\ne(2,1,6)$ なら $\Phi_n(a,b)>P(n)$ である。
証明は、まず次の 2 つの不等式を用意し、$a-b$ と $n$ の形で場合を分ける。
$p:=P(n)$ とおく。
場合 A:$a-b\ge2$.(i) と (ii)、および整数 $x\ge1$ についての $2^x\ge x+1$ により
$$
\Phi_n(a,b)>(a-b)^{\varphi(n)}\ge2^{\varphi(n)}\ge\varphi(n)+1\ge p
$$
である。
場合 B:$a-b=1$ で $p^2\mid n$.$n=p^kn'$($k\ge2$、$p\nmid n'$)とし、$n_0:=pn'$、$A:=a^{p^{k-1}}$、$B:=b^{p^{k-1}}$ とおく。円分多項式 の命題「円分多項式の基本の公式」の 2($p\mid m$ なら $\Phi_{pm}(x)=\Phi_m(x^p)$)を $k-1$ 回使い、両辺に $y$ の冪を掛けて同次化すると $\Phi_n(a,b)=\Phi_{n_0}(A,B)$ である。$A,B$ は互いに素で、$p^{k-1}\ge2$ なので $A-B\ge a^2-b^2=a+b\ge3$ である。$p\mid n_0$ なので (ii) を $n_0$ に使えて、場合 A と同じく $\Phi_{n_0}(A,B)>2^{\varphi(n_0)}\ge\varphi(n_0)+1\ge p$ である。
場合 C:$a-b=1$ で $n=pm$、$p\nmid m$.
C1($m=1$):$n=p\ge3$ で、$\Phi_p(a,b)=(a^p-b^p)/(a-b)=\sum_{i=0}^{p-1}a^{p-1-i}b^i$ である。$p$ 個の項はどれも $1$ 以上で、最初の項 $a^{p-1}$ は $2$ 以上なので、和は $p$ より大きい。
C2($m\ge2$):$m$ は $p$ より小さい素数を因数に持つので $p\ge3$ である。同じ命題の 3($p\nmid m$ なら $\Phi_{pm}(x)\Phi_m(x)=\Phi_m(x^p)$)を同次化すると $\Phi_n(a,b)\,\Phi_m(a,b)=\Phi_m(a^p,b^p)$ である(次数は $(p-1)\varphi(m)+\varphi(m)=p\varphi(m)$ で合う)。(i) により
$$
\Phi_n(a,b)=\frac{\Phi_m(a^p,b^p)}{\Phi_m(a,b)}>\left(\frac{a^p-b^p}{a+b}\right)^{\varphi(m)}=:R^{\varphi(m)}
$$
である。$b=a-1$ なので $a^p-b^p-a^{p-1}=a^{p-1}(a-1)-b^p=b(a^{p-1}-b^{p-1})>0$、すなわち $a^p-b^p>a^{p-1}$ である。
除外の $(2,1,6)$ では $\Phi_6(2,1)=4-2+1=3=P(6)$ で、下界の不等号は等号になる。
$n=2$ の場合.$a^2-b^2=(a-b)(a+b)$ の素因数 $p$ が原始素因数であることは、$p\mid a+b$ かつ $p\nmid a-b$ と同値である。奇素数 $p$ が $a+b$ と $a-b$ の両方を割れば、$p\mid2a$、$p\mid2b$ から $p\mid\gcd(a,b)=1$ となり矛盾するので、$a+b$ の奇素因数はすべて原始素因数である。一方 $a+b$ と $a-b$ の偶奇は一致するので、$2\mid a+b$ なら $2\mid a-b$ であり、$2$ は原始素因数にならない。よって原始素因数があることと、$a+b\ (\ge3)$ が奇素因数を持つこと、すなわち $2$ の冪でないことは同値である。
$n\ge3$ の場合.$a^n-b^n$ が原始素因数を持たないとする。lem-zsig-cyclo の 1 により $\Phi_n(a,b)$ は正の整数で、lem-zsig-nonprimitive により、その素因数はすべて $P(n)$ で、しかも 1 乗でしか現れない。よって $\Phi_n(a,b)\le P(n)$ である。lem-zsig-lower により、これは $(a,b,n)=(2,1,6)$ のときしか起こらない。逆に $(2,1,6)$ では、$2^6-1=3^2\cdot7$ で $3\mid2^2-1$、$7\mid2^3-1$ なので原始素因数がない。$\square$
証明は原始素因数の存在だけを示し、個数は教えない。$2^{11}-1=23\cdot89$ のように原始素因数が 2 つ以上あることもある。
$a>b\ge1$ を互いに素な整数、$n\ge2$ とする。$(a,b,n)\ne(2,1,3)$ なら、$a^n+b^n$ の素因数 $p$ で、$1\le k< n$ のどの $k$ についても $a^k+b^k$ を割らないものがある。
$2n\ge4$ なので、thm-zsig-main の除外 1 は当てはまらず、除外 2 は $2n=6$、$(a,b)=(2,1)$ すなわち $(a,b,n)=(2,1,3)$ にあたる。これを除けば $a^{2n}-b^{2n}$ の原始素因数 $p$ がある。$p\nmid a^n-b^n$ なので、$a^{2n}-b^{2n}=(a^n-b^n)(a^n+b^n)$ から $p\mid a^n+b^n$ である。$k< n$ で $p\mid a^k+b^k$ なら $p\mid a^{2k}-b^{2k}$ で、$2k< 2n$ なので原始性に反する。$\square$
$(2,1,3)$ では $2^3+1=9=3^2$ で、$3$ はすでに $2+1$ を割る。
$n\ge1$ について、$p\equiv1\pmod n$ を満たす素数 $p$ は無数にある。
$nk\ge3$、$nk\ne6$ となる $k\ge1$ ごとに、thm-zsig-main により $2^{nk}-1$ の原始素因数 $p_k$ がある。lem-zsig-order の 3 により、$p_k$ を法とする $2$ の位数は $nk$ で、$p_k\equiv1\pmod{nk}$、とくに $p_k\equiv1\pmod n$ である。位数が $k$ ごとに異なるので、$p_k$ は互いに異なる。$\square$
同じ主張の、円分多項式の値を使う別の証明が 円分多項式 の系「$n$ を法として $1$ に合同な素数の無限性」にある。
$q\ge2$ を素数の冪、$n\ge3$、$(q,n)\ne(2,6)$ とする。thm-zsig-main を $(a,b)=(q,1)$ に使うと、$q^n-1$ の原始素因数 $\ell$ がある。有限体 の定理「有限体の乗法群の構造」により $\mathbb F_{q^n}^\times$ は位数 $q^n-1$ の巡回群なので、位数 $\ell$ の元 $x$ がある。$\mathbb F_{q^n}$ の部分体で $\mathbb F_q$ を含むものは $\mathbb F_{q^d}$($d\mid n$)で(同記事の命題「有限体の部分体」)、$d< n$ なら $\ell\nmid q^d-1=\lvert\mathbb F_{q^d}^\times\rvert$ なので $x\notin\mathbb F_{q^d}$ である。よって $\mathbb F_q(x)=\mathbb F_{q^n}$ である。たとえば $q=2$、$n=4$ では $\ell=5$ で、$\mathbb F_{16}^\times$ の位数 $5$ の元はどれも $\mathbb F_{16}$ を $\mathbb F_2$ 上で生成する。一方 $(q,n)=(2,6)$ では $2^6-1=63$ の素因数 $3,7$ の位数の元はそれぞれ $\mathbb F_4$、$\mathbb F_8$ に入り、素数位数の元で $\mathbb F_{64}$ を生成するものはない。
| 外した仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| $\gcd(a,b)=1$(thm-zsig-main、$n\ge3$) | $(a,b,n)=(4,2,6)$ | 除外 2 にあたらないのに原始素因数がない |
| $\gcd(a,b)=1$(thm-zsig-main、$n=2$) | $(a,b,n)=(6,3,2)$ | $a+b=9$ は $2$ の冪でないのに原始素因数がない |
| $n\ge3$(lem-zsig-nonprimitive の 2) | $(a,b,n)=(7,1,2)$ | 原始でない素因数 $2$ が $\Phi_2(7,1)$ を 2 乗以上で割る |
| $p\nmid n$(lem-zsig-cyclo の 3 の後半) | $(a,b,n)=(2,1,6)$、$p=3$ | $\Phi_6(2,1)$ の素因数 $3$ が原始素因数でない |
1 行目:$4^6-2^6=2^6\cdot3^2\cdot7$ で、$2\mid4-2$、$3\mid4^2-2^2=12$、$7\mid4^3-2^3=56$ なので原始素因数がない。$a^n-b^n=g^n(a'^n-b'^n)$($g=\gcd(a,b)$)と書くと、$g$ の素因数はすでに $a-b$ を割るので、公約数があると原始素因数が見つけにくくなる。2 行目:$6^2-3^2=27=3^3$ の素因数は $3$ だけで、$3\mid6-3$ である。3 行目:$\Phi_2(7,1)=8=2^3$ で、$2\mid7-1$ なので $2$ は原始でない。4 行目:$\Phi_6(2,1)=3$ で、$3\mid2^2-1$ である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する