Zsigmondyの定理

定理解説整数整数-63

高校数学の美しい物語さんの記事

を初めて見たとき、一つだけ知らない定理がありました。それがZsigmondyの定理です：

Zsigmondyの定理 $a, b$ を互いに素な自然数とし、 $n$ を $2$ 以上の整数とする。このとき、 $2^6-1^6$ および $n=2$ かつ $a+b$ が $2$ の冪であるという例外ケースを除いて、 $a^n-b^n$ の或る素因数 $p$ が存在して、 $p$ は $1 \leq k \leq n-1$ なる任意の $k$ に対して $a^k-b^k$ を割り切らない。

この定理は1892年にZsigmondyによって発見・証明され、1904年にBirkhoffとVandiverによって再証明されています。この記事ではZsigmondyの定理のBirkhof-Vandiverによる証明をMichelsが整理したものを解説します。定理の主張を満たすような素因数のことを原始的素因数と呼ぶことにします。

準備の補題

自然数 $n$ に対して、 $\Phi_n(X)$ を第 $n$ 円分多項式とする。基本事項として

$\displaystyle X^n-1=\prod_{d\mid n}\Phi_d(X)$ ー①

および

$\displaystyle \Phi_n(X)=\prod_{d \mid n}(X^{\frac{n}{d}}-1)^{\mu(d)}$ ー②

が成り立つことを思い出します。ここで、 $\mu(d)$ はMöbius関数です。

補題１ $p$ を素数、 $n, k$ を自然数とする。このとき、

$\displaystyle \Phi_{p^kn}(X) = \begin{cases}\Phi_n(X^{p^k}) & p\mid n\\ \displaystyle \frac{\Phi_n(X^{p^k})}{\Phi_n(X^{p^{k-1}})} & p \nmid n \end{cases}$

が成り立つ。特に、任意の整数 $a$ に対して $\Phi_{p^kn}(a)$ は $\Phi_n(a^{p^k})$ を割り切る。

証明. ②を用いることによって容易に確認できる。 Q.E.D.

補題２ $p$ を素数とし、 $n=p^kq$ であるとする。ここで、 $k, q$ は自然数で $q$ は $p$ で割り切れない。このとき、整数 $a$ が $\Phi_n(a) \equiv 0 \pmod{p}$ を満たすならば、 $a \bmod{p}$ の乗法群 $\mathbb{F}_p^{\times}$ における位数は $q$ である。

証明. $p \mid \Phi_n(a)$ なので、①より $p \mid a^n-1$ である。Fermatの小定理より $a^n-1 \equiv a^q-1 \pmod{p}$ であり、結局 $p \mid a^q-1$ となる。すなわち、 $a \bmod{p}$ は確かに $\mathbb{F}_p^{\times}$ の元であって、その位数を $e$ とすると $e \mid q$ が成り立つ。補題１より $\Phi_n(a) \mid \Phi_q(a^{p^k})$ であり、Fermatの小定理より $\Phi_q(a^{p^k}) \equiv \Phi_q(a) \pmod{p}$ であるから $p \mid \Phi_q(a)$ ー③がわかる。 $e < q$ であると仮定して矛盾を導く。②より $a^e-1=\prod_{d \mid e}\Phi_d(a)$ なので、或る $d \mid e$ が存在して $p \mid \Phi_d(a)$ ー④が成り立つ。 $e < q$ であることから、③と④より多項式 $X^q-1=\prod_{r \mid q}\Phi_r(X)$ は $\mathbb{F}_p[X]$ に還元して考えると重根をもつことになる。しかしながら、重根を持てるのは $p \mid q$ の場合のみである。従って、我々は矛盾に到達した。 Q.E.D.

補題３ $n$ を自然数、 $a$ を整数とし、 $p$ を $\Phi_n(a)$ の素因数とする。このとき、 $p \equiv 1 \pmod{n}$ または $p \mid n$ のいずれかが成立する。

証明. これは鈴木の定理の記事105：円分多項式の係数と鈴木の定理 - INTEGERSにおける補題７に他ならない。 Q.E.D.

補題４(指数持ち上げ補題) $p$ を奇素数とし、 $p$ で割り切れない相異なる整数 $x, y$ が $x\equiv y \pmod{p}$ なる関係を満たすとき、任意の自然数 $n$ に対して

$\mathrm{ord}_p(x^n-y^n) = \mathrm{ord}_p(x-y)+\mathrm{ord}_p(n)$

が成り立つ。

証明. 別途記事を書いた:指数持ち上げ補題 - INTEGERS Q.E.D.

補題５ $n$ を自然数とし、 $x > 1$ を実数とする。このとき、不等式

$(x-1)^{\varphi(n)} \leq \Phi_n(x) < (x+1)^{\varphi(n)}$

が成り立つ。また、一つ目の不等式における等号は $n=2$ でのみ成立する。ここで、 $\varphi(n)$ はEulerのトーシェント関数である。

証明. $\zeta$ が絶対値 $1$ の複素数であれば三角不等式

$x-1 \leq \left|x-\zeta\right| \leq x+1$

が成立する。一つ目の不等式は $\zeta=1$ のときのみ、二つ目の不等式は $\zeta=-1$ のときのみ等号が成立する。この不等式を全ての $1$ の原始 $n$ 乗根について考えて掛け合わせることにより

$\displaystyle (x-1)^{\varphi(n)} \leq \prod_{\zeta}\left|x-\zeta\right| < (x+1)^{\varphi(n)}$

が得られる。一つ目の不等式で等号が成立するのは $\varphi(n)=1$ のときのみであり、それは $n=2$ のときである。二つ目の不等式は $x-1 < x+1$ であることから常に等号は成立しない。さて、定義より不等式の真ん中の数は $\left|\Phi_n(x)\right|$ であり、②より $x > 1$ であることから $\Phi_n(x) > 0$ である。 Q.E.D.

Zsigmondyの定理の証明

$a, b, n$ はZsigmondyの定理の主張に現れるようなものとして固定する。ただし、 $a > b$ とする(主張の本質は変わらない)。また、例外ケースではないと仮定する。

$n=2$ のとき $a^2-b^2=(a-b)(a+b)$ で、例外ケースでないことから $a+b$ は奇素数因子を持ち、それが原始的となる。何故ならば、もし、 $a-b$ も割り切るならば $a$ と $b$ を割り切ることになり互いに素であるという仮定に反するからである。

従って、以下 $n > 2$ とする。

若干の帰着
原始的素因数の存在を示すということは、 $a^n-b^n$ の素因数 $p$ が存在して $1 \leq k \leq n-1$ なる任意の $k$ に対して $p$ は $a^k-b^k$ を割り切らないことを示すということである(定義そのもの)。しかしながら、実際には

$a^n-b^n$ の素因数 $p$ が存在して、 $n$ の任意の真の約数 $d$ に対して $p$ が $a^d-b^d$ を割り切らなければ $p$ は原始的素因数である。

が成り立つ。これを確認するには $a^n-b^n$ の素因数 $p$ に対して、 $p$ が $a^k-b^k$ の素因数であるような最小の自然数 $k$ をとったときに $k \mid n$ となっていることを示せばよい。 $a, b$ は互いに素であるからともに $p$ で割り切れないことに注意する。 $bc \equiv 1 \pmod{p}$ なる整数 $c$ を一つとる*1。 $p \mid a^k-b^k$ は $p \mid (ac)^k-1$ と同値である。よって、 $k$ の最小性から $ac\bmod{p}$ の $\mathbb{F}_p^{\times}$ における位数は $k$ である。 $p \mid (ac)^n-1$ でもあるから $k \mid n$ がわかる。

証明方針

$\Phi_n(X, Y)$ を斉次円分多項式とする。すなわち、

$\displaystyle \Phi_n(X, Y) = Y^{\varphi(n)}\Phi_n\left( \frac{X}{Y} \right)$ ー⑤

$\displaystyle X^n-Y^n=\prod_{d \mid n}\Phi_d(X, Y)$ ー⑥

$\displaystyle \Phi_n(X, Y) = \prod_{d \mid n}(X^{\frac{n}{d}}-Y^{\frac{n}{d}})^{\mu (d)}$ ー⑦

が成り立つ。円分多項式に関する命題は大抵の場合斉次版に書き換えることができる。

示したいことは $a^n-b^n$ が原始的素因数を持つことであるが、 $a^n-b^n$ の因数のうち原始的素因数からなる部分を $P_n$ とする。すなわち、 $\mathcal{P}$ を $a^n-b^n$ の原始的素因数全体からなる集合とするとき、

$\displaystyle P_n:=\prod_{p \in \mathcal{P}}p^{\mathrm{ord}_p(a^n-b^n)}$

と定義される。 $\mathcal{P}=\emptyset$ ならば $P_n:=1$ とする。しからば、我々が示すべきことは $P_n > 1$ となる。

ところで、各原始的素因数は⑥より $d\mid n$ なる $d$ に対する $\Phi_d(a, b)$ のいずれかに住んでいるが、原始的素因数の定義と⑦を合わせて考えると $d < n$ なる $d$ に対する $\Phi_d(a, b)$ には住んでいないことがわかる。すなわち、 $P_n$ は $\Phi_n(a, b)$ に格納されているのである。そこで、

$\Phi_n(a, b)=\lambda_nP_n$

と $\lambda_n$ を導入する。我々は $P_n$ 自体を攻めるのではなく、 $\lambda_n$ を攻めるという方針をとることにする。証明のKeyは $\lambda_n$ は殆ど素因数を持ち得ないことを示すことである。具体的にいうと、 $\lambda_n$ は素因数を持ったとしても高々一つであり、更にその素因数の指数は $1$ であることを示すことができる。この証明に指数持ち上げ補題が巧みに用いられることになる。そうして、 $\lambda_n$ が十分に小さいことを示した後に補題５を使って $\Phi_n(a, b)$ を下から評価することによって $P_n$ も下から評価できるという寸法である。

$\lambda_n$ の構造

$\lambda_n$ が素因数 $p$ を持ったと仮定する。このとき、

$p \mid n$ を示す。 $p=2$ のときは補題３のうち、 $p \equiv 1 \pmod{n}$ は成り立たない( $n > 1$ なので)。よって、 $p \mid n$ が成り立つ。

$p$ は奇素数であるとする。 $p \nmid n$ と仮定して矛盾を導く。 $\lambda_n$ の素因数は原始的ではないため、「若干の帰着」の内容と合わせると、 $d \mid n$ , $d < n$ であって $p \mid a^d-b^d$ なるものが存在する。まず、⑥より

$\displaystyle \Phi_n(a, b) \left| \ \frac{a^n-b^n}{a^d-b^d} \right.$

であり、特に

$\displaystyle p \left| \ \frac{a^n-b^n}{a^d-b^d} \right.$ ー⑧

であることがわかる。一方、 $a^d \equiv b^d \pmod{p}$ であって $d \mid n$ であるから、指数持ち上げ補題を適用すると

$\mathrm{ord}_p(a^n-b^n) = \mathrm{ord}_p(a^d-b^d)$

が成り立つことがわかる( $p \nmid n$ と仮定していることに注意)。これは⑧と矛盾する。以上により $p \mid n$ が示された。つまり、 $\lambda_n$ の素因数は $n$ の素因数によって支配される(とりあえずそんなにたくさんはないことがわかった)。 $p \mid \lambda_n$ を引き続き仮定する。

$\lambda_n$ の素因数は $p$ のみであることを示す。 $n=p^kq$ と表示する。ここで、 $k, q$ は自然数で $q$ は $p$ で割り切れない。補題１は斉次版でも成り立つため

$\Phi_n(a, b) \mid \Phi_q(a^{p^k}, b^{p^k})$

が成り立ち、Fermatの小定理より $\Phi_q(a^{p^k}, b^{p^k}) \equiv \Phi_q(a, b) \pmod{p}$ であるから、 $p \mid \Phi_q(a, b)$ である。 $bc \equiv 1 \pmod{p}$ なる整数 $c$ をとると $p \mid \Phi_q(ac)$ が成り立つので、補題３より $p \equiv 1 \pmod{q}$ または $p \mid q$ となる。今、 $p \nmid q$ であるから $p \equiv 1 \pmod{q}$ が成立することがわかる。特に、 $p > q$ である。 $r$ を $n$ の $p$ 以外の素因数としよう(これは $q\neq 1$ のときのみ考える)。すると、 $r \mid q$ なので、 $p > q$ と合わせて $p > r$ でなければならない。先ほど $p \mid n$ を示したことと合わせて

$\lambda_n$ の素因数は存在すれば $n$ の素因数のうち最大のものとして特徴付けられる。特に、 $\lambda_n$ の素因数はあったとしても一つである

ことが示された。引き続き $p \mid \lambda_n$ と仮定しよう。今示したことから $\lambda_n=p^j$ と書けることがわかる。

$j=1$ であることを示す。 $p=2$ のときから示す。 $n$ の最大の素因数が $2$ ということになるので、 $n$ は $2$ の冪である。 $n > 2$ としているのだから、 $n/2$ も $2$ の冪である。⑦とMöbius関数の性質より

$\displaystyle \Phi_n(a, b) = \frac{a^n-b^n}{a^{\frac{n}{2}}-b^{\frac{n}{2}}} = a^{\frac{n}{2}}+b^{\frac{n}{2}}$

である。 $a, b$ が互いに素であることと $2 \mid \lambda_n \mid \Phi_n(a, b)$ から $a$ と $b$ はともに奇数である。すなわち、 $\Phi_n(a, b)$ は奇数の平方数の和になっていることがわかった。従って、 $\Phi_n(a, b) \equiv 2 \pmod{4}$ である。すなわち、 $\Phi_n(a, b)$ は単偶数(i.e. $j=1$ )である。

次に $p$ が奇素数であるとする。 $p \mid a^d-b^d$ なる $d \mid n$ を任意に考える。今までと同じように $c$ をとると、 $p \mid \Phi_n(a, b)$ であることから $p \mid \Phi_n(ac)$ であることがわかり、補題２より $ac\bmod{p}$ の $\mathbb{F}_p^{\times}$ での位数は $q$ である( $n=p^kq$ という設定は続ける)。一方、 $p \mid (ac)^d-1$ なので、 $q \mid d$ であることがわかる。このことから、⑦を考えると

$j=\mathrm{ord}_p(\lambda_n) = \mathrm{ord}_p(\Phi_n(a, b))=\mathrm{ord}_p(a^n-b^n)-\mathrm{ord}_p(a^{\frac{n}{p}}-b^{\frac{n}{p}})$

となる( $\mu$ の値が $0$ とならない因子のみを考えればよく、そのようなもののうち最後の二つ以外は $p$ で割れない)。 $p$ が原始的でないことを考えると、上の議論と合わせて $a^{\frac{n}{p}}-b^{\frac{n}{p}}$ は実際に $p$ で割り切れることがわかるので、 $x=a^{\frac{n}{p}}$ , $y=b^{\frac{n}{p}}$ , $n=p$ として指数持ち上げ補題を適用することができる。従って、

$j=\mathrm{ord}_p(a^n-b^n)-\mathrm{ord}_p(a^{\frac{n}{p}}-b^{\frac{n}{p}})=\mathrm{ord}_p(p)=1$

を得る。以上をもって、 $\lambda_n$ は $1$ であるか、或る素数 $p$ に対して $\lambda_n=p$ となることが示された。

証明の完結

$\lambda_n=1$ のとき補題５( $n > 2$ に注意)より

$P_n = \Phi_n(a, b) > (a-b)^{\varphi(n)} \geq 1$

よって、 $P_n > 1$ が示された。

$\lambda_n=p, a-b > 1$ のとき補題５より

$\displaystyle P_n= \frac{1}{p}\Phi_n(a, b) > \frac{1}{p}(a-b)^{\varphi(n)} \geq \frac{2^{p-1}}{p} \geq 1$

となって、 $P_n > 1$ が示された( $p \mid n$ なので $\varphi(n) \geq p-1$ )。

$\lambda_n=p, a-b = 1$ のとき $\Phi_n(a, b) > p$ を示せばよい。 $p \mid a^n-b^n$ なので $p$ は奇数である(今、 $a, b$ のパリティは異なる)。 $n=p^kq$ とおく。いつも通り $k, q$ は自然数で $q$ は $p$ で割り切れないものとする。 $k > 1$ と仮定する。 $n=p^{k-1}pq$ と考えて補題１の斉次版を適用すると