今回は数論（Number Theory）に関する定理、「Zsigmondy’s Theorem」（ジグモンディの定理）を取り上げます。
国際数学オリンピックなどの問題は、日本における大学入試の数学とは何というか「種類」が違うような気がします。例として今年2017年のＩＭＯ（国際数学オリンピック）の第１問を挙げてみます（この問題は今回の話題のテーマではないので特に解説はしません。悪しからず･･･）。
《ＩＭＯ 2017 Problem １》
For each integer $a_0 > 1$, define the sequence $a_0, a_1, a_2, \ldots$ for $n \geq 0$ as$$a_{n+1} = \begin{cases}\sqrt{a_n} & \text{if } \sqrt{a_n} \text{ is an integer,} \\a_n + 3 & \text{otherwise.}\end{cases}$$Determine all values of $a_0$ such that there exists a number $A$ such that $a_n = A$ for infinitely many values of $n$.
（2017年 IMO 第１問）
実は本問は（ＩＭＯの問題としては）大して難しい問題ではないのですが、一般的な日本の高校生が取り組んでみて歯が立つかというと、そんなことはないでしょう。ＩＭＯなどの数学コンテストはこういった思考力や発想力を要する問題がほとんどを占めています。
一方で、ＩＭＯでは予備知識としてある程度高尚な(？)定理を証明せずに使用して良いことになっています。例えば次のようなフェルマーの小定理などは言ってみれば「常識」扱いされています。
| 『フェルマーの小定理（Fermat’s Little Theorem）』
$p$を素数、$a$を$p$と互いに素な整数とするとき$$a^{p-1} \equiv 1 \ \pmod{p}$$が成立する。 |
では、次のような問題を片づける際にはどのようなアプローチが有効なのでしょうか。
《問題》
Prove that the sequence $a_n=3^n-2^n$ contains no three numbers in geometric progression.
（1994年 Romania 第1回TST 第3問）
和訳すると
「数列 $a_n=3^n-2^n$ は等比数列となる３項を含まないことを示せ」
となります。なお、ここでいう等比数列となる３項というのは別に連続している３項に限りません。この問題は「数列$\{a_n\}$を $a_n=3^n-2^n$ で定めるとき、$x<y<z$ である正の整数$x$、$y$、$z$について、等比数列を成すような$a_x$、$a_y$、$a_z$が存在しないことを示せ」という問題と同義です。そこでこの３項が等比数列を成すとすると、$${a_y}^2=a_x a_z$$ $$\therefore (3^y-2^y)^2=(3^x-2^x)(3^z-2^z) \tag{1}$$が成り立ちます。
･･･さて、ここで以下の定理が極めて有効です。
『ジグモンディの定理（Zsigmondy’s Theorem）』$a$と$b$が互いに素な整数で $a>b$ であるとき、任意の正の整数$n$に対して、$a^n-b^n$ を割り切るが $a^k-b^k$ $(1 \leqq k \leqq n-1)$ を割り切らないような素数（primitive prime divisor）が少なくとも１つ存在する。但し以下の例外を除く。 ・$n=1$ かつ $a-b=1$ のとき |
式$(1)$からの論述が解答者の腕の見せ所なのですが、ここではこの「ジグモンディの定理」を用いて鮮やかに解答してみたいと思います。
《解答例》
$x<y<z$ となる正の整数$x$、$y$、$z$について、$a_x$、$a_y$、$a_z$の３項が等比数列を成すとする。このとき、$${a_y}^2=a_x a_z$$ $$\therefore (3^y-2^y)^2=(3^x-2^x)(3^z-2^z)$$が成り立つ。ここでジグモンディの定理より、$3^y-2^y$ を割り切らないが $3^z-2^z$ を割り切るような素数$p$が存在する。右辺が$p$の倍数であるのに左辺が$p$の倍数でないから不合理である。よってこのような正の整数$x$、$y$、$z$は存在しない。よって数列 $a_n=3^n-2^n$ は等比数列となる３項を含まないことが示された。
どうでしょうか？この定理の力が遺憾なく発揮されていますね。このように普通に解くと難しい、若しくは面倒くさい問題であってもアッという間に片付けることができてしまいます。まさに”overkill”と言ったところですね。
冪の差の形で成り立つこの定理、実は和の形でも成り立つことが知られています。和のバージョンは差のバージョンで偶数乗を考えることにより導くことができます。
『和のジグモンディの定理（Zsigmondy’s Theorem for sum）』$a$と$b$が互いに素な整数で $a>b$ であるとき、任意の正の整数$n$に対して、$a^n+b^n$ を割り切るが $a^k+b^k$ $(1 \leqq k \leqq n-1)$ を割り切らないような素数（primitive prime divisor）が少なくとも１つ存在する。但し以下の例外を除く。 ・$n=3$ かつ $a=2$、$b=1$ のとき |
これまた強力なツールですね。･･･ということで以下の問題を解いてみましょう。
《問題》
Find all triplets of positive integers $(a,m,n)$ such that $a^m+1$ divides $(a + 1)^n$.
（2000年 IMO SLP）
和訳すると
「$a^m+1$ が $(a + 1)^n$ を割り切るような３つの正の整数の組$(a,m,n)$をすべて求めよ」
となります。「ジグモンディの定理」による解答例は以下の通り。
《解答例》
まず、$a=1$ のとき任意の$m,n$について $a^m+1$ は $(a + 1)^n$ を割り切る。また $m=1$ のとき任意の$a,n$について $a^m+1$ は $(a + 1)^n$ を割り切る。ここで $(a,m)=(2,3)$ は $n \geqq 2$ に対して適解であるので、$(a,m) \ne (2,3)$ の場合を考える。このときジグモンディの定理より、$a^m+1$ は $a+1$ を割り切らない素因数を持つから $a^m+1$ が $(a + 1)^n$ を割り切ることはない。よって $(a,m) \ne (2,3)$ のとき解は存在しない。故に求める解の組み合わせは$$\{(a,1,n),(1,m,n) \mid a,m,n \in \mathbb{N}\} \cup \{(2,3,n) \mid n \in \mathbb{N} \geqq 2\}$$となる。
$a+1$ は $a^1+1^1$ と見なせばジグモンディの定理が利用できますね。この問題も普通に解くとそれなりに骨が折れるのですが、ジグモンディの定理により大幅に省力化できます。
この定理を使えば、例えば2011年のJMO（日本数学オリンピック）本選の第2問も簡単に片付いてしまいます。
《問題》
正の整数の組$(a,n,p,q,r)$であって、等式$$a^n-1=(a^p-1)(a^q-1)(a^r-1)$$をみたすものをすべて求めよ。
（2011年 日本数学オリンピック 本選 第2問）
ジグモンディの定理により、$a \geqq 3$ かつ $n \geqq 3$ のとき、$a^n-1$ は「primitive prime divisor」を持つため解は存在しないことが分かります（$a=3$ のときは解を持つ）。これより場合分けがかなりラクになります。答えは$(1,n,p,q,r)$、$(2,n,n,1,1)$、$(2,n,1,n,1)$、$(2,n,1,1,n)$、$(2,6,3,2,2)$、$(2,6,2,3,2)$、$(2,6,2,2,3)$、$(3,2,1,1,1)$（文字は任意の正の整数値をとる）となります。
冪に関する問題に対しては万能とも思えるジグモンディの定理にも使いどころというものがあります。例えば以下のような問題には利用することが難しいでしょう。
《問題》
Prove that for every nonnegative integer $n$, in the prime factorization of the number $7^{7^{n}}+1$, the sum of the exponents is at least $2n+3$.
（2007年 USAMO 第5問）
和訳すると
「任意の非負整数$n$について、$7^{7^{n}}+1$ を素因数分解したときのすべての指数の和は少なくとも $2n+3$ であることを示せ」
となります。２つの累乗数の和なのでジグモンディの定理が適用できそうですが、ジグモンディの定理の主張ではせいぜい$n$個の素因数の存在しか言えません。この問題では与式を地道に因数分解する必要があります（解答の際に $7^{n-1}+1$ が偶数であることを利用しますが、詳細は割愛させて頂きます･･･）。
● ● ● ● ●
さて、このジグモンディの定理、とある数列に関して面白い応用できるのですが、その話は次回に持ち越すことにしましょう。