インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

Zsigmondyの定理

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

mathtrain.jp

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

Zsigmondyの定理 a, bを互いに素な自然数とし、n2以上の整数とする。このとき、2^6-1^6およびn=2かつa+b2の冪であるという例外ケースを除いて、a^n-b^nの或る素因数pが存在して、p1 \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関数です。

補題1 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.

補題2 pを素数とし、n=p^kqであるとする。ここで、k, qは自然数でqpで割り切れない。このとき、整数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が成り立つ。補題1より\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.

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

証明. これは鈴木の定理の記事
integers.hatenablog.com
における補題7に他ならない。 Q.E.D.

補題4(指数持ち上げ補題) pを奇素数とし、pで割り切れない相異なる整数x, yx\equiv y \pmod{p}なる関係を満たすとき、任意の自然数nに対して
\mathrm{ord}_p(x^n-y^n) = \mathrm{ord}_p(x-y)+\mathrm{ord}_p(n)
が成り立つ。

証明. 別途記事を書いた:
integers.hatenablog.com
Q.E.D.

補題5 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 |x-\zeta| \leq x+1

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

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

が得られる。一つ目の不等式で等号が成立するのは\varphi(n)=1のときのみであり、それはn=2のときである。二つ目の不等式はx-1 < x+1であることから常に等号は成立しない。さて、定義より不等式の真ん中の数は|\Phi_n(x)|であり、②より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も割り切るならばabを割り切ることになり互いに素であるという仮定に反するからである。

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

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

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

が成り立つ。これを確認するにはa^n-b^nの素因数pに対して、pa^k-b^kの素因数であるような最小の自然数kをとったときにk \mid nとなっていることを示せばよい。a, bは互いに素であるからともにpで割り切れないことに注意する。bc \equiv 1 \pmod{p}なる整数cを一つとる*1p \mid a^k-b^kp \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_n(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が十分に小さいことを示した後に補題5を使って\Phi_n(a, b)を下から評価することによってP_nも下から評価できるという寸法である。

\lambda_nの構造

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

p \mid nを示す。 p=2のときは補題3のうち、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は自然数でqpで割り切れない。補題1は斉次版でも成り立つため

\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)が成り立つので、補題3よりp \equiv 1 \pmod{q}またはp \mid qとなる。今、p \nmid qであるからp \equiv 1 \pmod{q}が成立することがわかる。特に、p > qである。rnp以外の素因数としよう(これは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ということになるので、n2の冪である。n > 2としているのだから、n/22の冪である。⑦と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)からabはともに奇数である。すなわち、\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)であることがわかり、補題2より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_n1であるか、或る素数pに対して\lambda_n=pとなることが示された。

証明の完結

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

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

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

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

\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は自然数でqpで割り切れないものとする。k > 1と仮定する。n=p^{k-1}pqと考えて補題1の斉次版を適用すると

\Phi_n(a, b) = \Phi_{pq}(a^{p^{k-1}}, b^{p^{k-1}})

が成り立ち、

\displaystyle \Phi_{pq}(a^{p^{k-1}}, b^{p^{k-1}}) \geq (a^{p^{k-1}}-b^{p^{k-1}})^{\varphi(pq)} \geq a^p-b^p = \sum_{i=0}^{p-1}\binom{p}{
i}b^i > p

と評価できる。k=1、すなわちn=pqの場合を考える。補題1の斉次版と補題5の斉次版より

\displaystyle \Phi_n(a, b) = \frac{\Phi_q(a^p, b^p)}{\Phi_q(a, b)} > \frac{(a^p-b^p)^{\varphi(q)}}{(a+b)^{\varphi(q)}} \geq \frac{a^p-b^p}{a+b}

と評価できる。p \geq 3のとき関数y=\frac{(x+1)^p-x^p}{x}x \geq 1で単調増加なので、

\displaystyle  \Phi_n(a, b) > \frac{a^p-b^p}{a+b} \geq \frac{(2^p-1)b}{2b+1} \geq \frac{2^p-1}{3}

となるが、p > 3だとこれはpより大きい。こうして、p=3の場合が残った。n=pqで、前に示したようにq < p=3なのだから、n=3, 6しかありえない。

n=3としよう。a^3-b^3=(a-b)(a^2+ab+b^2)=a^2+ab+b^2 > 1なので、a^2+ab+b^2の素因数は原始的である(「若干の帰着」に注意)。最終的にn=6の場合が残ったが、

\displaystyle \Phi_6(a, b) = \frac{(a^6-b^6)(a-b)}{(a^2-b^2)(a^3-b^3)} = \frac{a^3+b^3}{a+b} = a^2-ab+b^2 = b^2+b+1

なので、b > 1ならば\Phi_6(a, b) > 3=pが示される。b=1, a=2のときは、例外ケースであった。 Q.E.D.

あとがき

Zsigmondyの定理は古い結果ですが、今ではZsigmondyの定理を特殊な場合として含む、はるかに強力な結果が得られています:
integers.hatenablog.com

この記事を書いたことによって、インテジャーズでは高校数学の美しい物語さんの「整数論の美しい定理7つ」の記事で紹介されている7つの定理のうち、フェルマーの最終定理以外の証明を解説したことになります。あと一つ!

*1:cの存在証明は integers.hatenablog.com に書きました。