2017-04-02

ソフィー・ジェルマンの定理

定理解説整数整数-197

Fermatの最終定理に関するSophie Germainの定理とその証明を解説します。

前回の記事でSophie Germainによるグランドプランが失敗に終わったことを紹介しました：

integers.hatenablog.com

しかし、彼女は転んでもただでは起きません。

奇素数 $p$ を固定します。グランドプランは「非隣接条件を満たすような $p$ の補助素数の無限性を示そう」というもので、事実は「有限個しか存在しない」というものでした。そこで、彼女が到達したのは

「非隣接条件にもう一つ条件を加えた $p$ の補助素数が一つでも存在すれば、FLT( $p$ )のファーストケースは解決する」

というものです。まず、Sophie Germain以降、FLT( $p$ )はファーストケースとセカンドケースに分けて考えられることが多いです。

FLT( $p$ )のファーストケース $p$ を奇素数とする。 $x^p+y^p=z^p$ を満たすような $p$ で割れない整数 $x, y, z$ は存在しない。

FLT( $p$ )のセカンドケース $p$ を奇素数とする。 $x^p+y^p=z^p$ を満たすような $0$ でない整数 $x, y, z$ であって、 $p \mid xyz$ を満たすものは存在しない。

ファーストケースとセカンドケースでは難しさが異なり(セカンドケースの方が難しい)、成果が少なかった時代においては、ファーストケースだけでもとりあえず解ければ大きな進展であると考えてよいでしょう。

そうして、グランドプランは失敗に終わったものの、Sophie GermainはFLT( $p$ )のファーストケースを解決する $p$ に関する十分条件を与えたのです。これは立派な定理であると言え、FLT研究における最初のブレイクスルーでした。

定理を具体的に述べると次のようになります。実際にはファーストケースよりも強いことを示しています：

Sophie Germainの定理 $p$ を奇素数とする。 $p$ の補助素数 $\theta$ であって、非隣接条件を満たし、更に $p$ が $\bmod{\theta}$ における $p$ 冪剰余とはならないようなものが存在したと仮定する。このとき、 $x^p+y^p=z^p$ を満たすような整数 $x, y, z$ が存在すれば、 $x, y, z$ の少なくとも一つは $p^2$ で割り切れなければならない。

文献によっては $p^2$ に対する結果はLegendreによるものとされることもあるそうですが、Sophie Germainは確かに $p^2$ に対する結果を得ており、そのことをLegendreも明記しているとのことです。

Sophie Germainは定理の仮定を満たすような補助素数を具体的に計算することにより、 $197$ 未満の奇素数に対してはファーストケースが成立することを確認しています。

定義 (Sophie Germain素数) 素数 $p$ がSophie Germainであるとは、 $2p+1$ が素数であるときにいう。

次の系がSophie Germainの定理と呼ばれることが多いです：

系 $p$ がSophie Germain素数であれば、FLT( $p$ )のファーストケースが成立する。

これを言うには、 $p$ がSophie Germain素数であるときに $2p+1$ が定理の仮定を満たすような $p$ の補助素数であることを示せば十分です：

$\theta := 2p+1$ とする。このとき、 $\theta-1=2p$ なので、Fermatの小定理により $\theta$ で割り切れないような任意の整数 $a$ は

$a^{2p} \equiv 1 \pmod{\theta}$

すなわち、 $a^p \equiv \pm 1 \pmod{\theta}$ を満たす。これより、 $a^p \equiv p \pmod{\theta}$ とは成り得ないことがわかり、 $p$ は $\bmod{\theta}$ における $p$ 冪剰余ではない。また、 $\theta$ が非隣接条件を満たさなければ

$1+a^p \equiv b^p \pmod{\theta}$

を満たすような $\theta$ で割り切れない整数 $a, b$ が存在することになるが、

$1\pm 1 \equiv \pm 1 \pmod{\theta}$

と言っていて、それはあり得ない。 Q.E.D.

定理の証明

奇素数 $p$ に対して定理の仮定が満たされ、 $0$ でない整数 $x, y, z$ が $x^p+y^p=z^p$ を満たしていると仮定する。FLTでは毎度の如く、 $x, y, z$ はどの二つをとっても互いに素であると仮定してよい。

$\displaystyle \varphi(X, Y) := \frac{X^p+Y^p}{X+Y}, \quad \psi(X, Y) := \frac{X^p-Y^p}{X-Y}$ とおく。

主張１ $x+y$ と $\varphi(x, y)$ は $p$ 以外の共通因子を持たない。同様に、 $z-x$ と $\psi(z, x)$ 、 $z-y$ と $\psi(z, y)$ もそれぞれ $p$ 以外の共通因子を持たない。

証明. $p$ とは異なる素数 $q$ が $x+y$ と $\varphi(x, y)$ を割り切ると仮定する。このとき、 $y \equiv -x \pmod{q}$ であるから

$\varphi(x, y) = x^{p-1}-x^{p-2}y+x^{p-3}y^2- \cdots +y^{p-1} \equiv px^{p-1} \pmod{q}$

を得る。 $p \mid \varphi(x, y)$ であることと $q \neq p$ であることから $q \mid x$ となり、 $q \mid x+y$ と合わせると $q \mid y$ 。これは $x, y$ が互いに素であるという仮定に反する。残りの場合も同様。 Q.E.D.

主張２ $p$ は $x, y, z$ のどれかを割り切る。

証明. $p$ が $x, y, z$ を割り切らないと仮定して背理法で証明する。

$(x+y)\varphi(x, y) = x^p+y^p = z^p$

であり、 $p \nmid z$ であることから主張１より $x+y$ と $\varphi(x, y)$ は互いに素であることがわかる。よって、整数 $A, s$ が存在して

$x+y=A^p, \quad \varphi(x, y) = s^p$

が成り立つ。同様にして、整数 $B, C, t, u$ が存在して

$\begin{align} &z-x = B^p, \quad \psi(z, x) = t^p \\ &z-y = C^p, \quad \psi(z, y)=u^p\end{align}$ −①

が成り立つ。 $\theta$ を定理の仮定を満たすような $p$ の補助素数とする。非隣接条件を満たすことから、 $\theta$ は $x, y, z$ の少なくとも一つを割り切る(前記事の補題１)。 $\theta \mid z$ としても一般性を失わない。すると、

$2z = (x+y)+(z-x)+(z-y) = A^p+B^p+C^p \equiv 0 \pmod{\theta}$

となるので、非隣接条件から $A, B, C$ の少なくとも一つは $\theta$ で割り切れることがわかる。もし、 $\theta \mid B$ であれば、 $x=z-B^p$ も $\theta$ で割れることになり $x, z$ が互いに素であることに反する。よって、 $\theta \nmid B$ 。同様に $\theta \nmid C$ 。したがって、 $\theta \mid A$ でなければならない。

$x+y=A^p$ なので、 $y \equiv -x \pmod{\theta}$ 。これより

$s^p = \varphi(x, y) \equiv px^{p-1} \pmod{\theta}$ −②

一方、 $B^p=z-x \equiv -x \pmod{\theta}$ であることから、 $x$ は $\bmod{\theta}$ における $p$ 冪剰余である。 $p$ も $x$ も $\theta$ では割れないのだから、②より $p$ は $p$ 冪剰余となる。これは $\theta$ に関する定理の仮定に反する。 Q.E.D.

主張２により $p$ は $x, y, z$ のいずれかを割り切るが、 $p \mid z$ であると仮定しても一般性を失わない(すると、 $x, y$ は $p$ では割れない)。この仮定のもとで次が成り立つ：

主張３ $z$ は実は $p^2$ で割り切れる。

証明. $x+y=w$ とおく。すると、

$\displaystyle \varphi(x, y) = \frac{(w-x)^p+x^p}{w} = w^{p-1}-\binom{p}{1}w^{p-2}x+\cdots + \binom{p}{p-1}x^{p-1}$

と展開できるが、Fermatの小定理より $w \equiv x^p+y^p = z^p \equiv 0 \pmod{p}$ であるから、

$\varphi(x, y) \equiv px^{p-1} \pmod{p^2}$

がわかる。これはすなわち、 $\varphi(x, y)$ は $p$ では割り切れるが $p^2$ では割り切れないことを意味する。従って、 $(x+y)\varphi(x, y)=z^p$ および主張１より整数 $A, s$ が存在して

$x+y=p^{p-1}A^p, \quad \varphi(x, y) = ps^p$

が成り立つことが分かる。一方、①はこの場合にもそのまま成り立つ。すると、

$B^p+C^p = 2z-(x+y) \equiv 0 \pmod{p}$

であり、これは $B^p \equiv -C^p \pmod{p^2}$ を導く！*1

$p^2 \mid x+y$ および $p^2 \mid B^p+C^p$ がわかったので、

$2z = B^p+C^p+(x+y) \equiv 0 \pmod{p^2}$ .

これは $p^2 \mid z$ を示している。 Q.E.D.

以上でSophie Germainの定理の証明が完了します。

参考記事

R. Laubenbacher, D. Pengelley, "Voici ce que j'ai trouve": Sophie Germain's grand plan to prove Fermat's Last Theorem.

C. Alkalay-Houlihan, Sophie Germain and Special Cases of Fermat’s Last Theorem.

以下の記事でSophie Germain素数を取り扱ったことがあります。

integers.hatenablog.com

*1:一見、 $B^p \equiv -C^p \pmod{p}$ から $B^p \equiv -C^p \pmod{p^2}$ を導いており、「そんな馬鹿な。。」と思われるかもしれませんが、証明は簡単です。Fermatの小定理より $B^p \equiv -C^p \pmod{p}$ から $B \equiv -C \pmod{p}$ が導かれますが、すなわち、 $B=-C+jp$ なる整数 $j$ が取れるので、これの $p$ 乗を二項展開すればわかります。

2017-04-01

フェルマーの最終定理解決への"グランドプラン"

整数整数-7 整数-13

Sophie Germainは1776年4月1日にパリで生まれた女性数学者です。

彼女のよく知られた仕事はFermatの最終定理(FLT)への貢献です。彼女がFLTへ挑戦した時点では $n=3, 4$ の場合しか証明されていませんでした。

なお、FLT( $3$ )を証明したのはEulerでFLT( $4$ )を証明したのはFermatです。証明は

integers.hatenablog.com

の付録で読むことができます。歴史的には1823年にLegendre、1825年にDirichletがFLT( $5$ )を、1839年にLameがFLT( $7$ )を証明しています。

Sophie Germainは個別の $p$ に対するFLT( $p$ )を解くのではなく、全ての素数でFLTを解決することを目論みました。この記事では彼女の"グランドプラン"とその失敗について解説します。

Sophie Germainのグランドプラン

$p$ を奇素数とします。このとき、 $\theta$ が $p$ の補助素数であるとは、 $\theta$ が素数であり、なおかつ或る正整数 $n$ で $\theta=2np+1$ と書けるときに言います。

定義 $\theta$ を $p$ の補助素数とする。 $\bmod{\theta}$ の完全代表系 $\{0, 1, 2, \dots, \theta-1=2np\}$ を考えた際に、 $0$ を除いた $1, 2, \dots, 2np$ のうち $\bmod{\theta}$ で $p$ 冪剰余になっているもの全体を取り出す。それらが隣合う二数を含まないとき、 $\theta$ は非隣接条件を満たすという。

例１) $p=3$ の補助素数 $7, 13$ は非隣接条件を満たすが、補助素数 $19$ は非隣接条件を満たさない。

$\{1^3, 2^3, 3^3, 4^3, 5^3, 6^3\} = \{1, 8, 27, 64, 125, 216\} \equiv \{1, 6\} \pmod{7}$

$\{1^3, 2^3, \dots, 12^3\} \equiv \{1, 5, 8, 12\} \pmod{13}$

$\{1^3, 2^3, \dots, 18^3\} \equiv \{1, \color{red}{7}, \color{red}{8}, \color{blue}{11}, \color{blue}{12}, 18\} \pmod{19}$

例２) $p=5$ の補助素数 $11$ は非隣接条件を満たすが、補助素数 $31$ は非隣接条件を満たさない。

$\{1^5, 2^5, \dots, 10^5\} \equiv \{1, 10\} \pmod{11}$

$\{1^5, 2^5, \dots, 30^5\} \equiv \{1, 5, 6, \color{red}{25}, \color{red}{26}, 30\} \pmod{31}$

Sophie GermainはFLTを解決するためのグランドプランを1819年3月12日のGaussへの手紙に綴っています。グランドプランの最終目標は次を証明することでした。

グランドプランの最終目標 任意の奇素数 $p$ に対して非隣接条件を満たすような $p$ の補助素数が無数に存在することを証明する。

実際、この最終目標が達成されるとFLTが解決することを彼女は証明しています。

補題１ $p$ を奇素数とし、 $\theta$ を非隣接条件を満たす $p$ の補助素数とする。 $x^p+y^p=z^p$ を満たすような整数 $x, y, z$ が存在した場合、それらのうち少なくとも一つは $\theta$ で割り切れる。

証明. $x, y, z$ がいずれも $\theta$ で割り切れないと仮定しよう。 $a$ を $x$ の $\bmod{\theta}$ における逆元とする*1。このとき、

$1+(ay)^p \equiv (az)^p \pmod{\theta}$

が成り立ち、 $ay$ と $az$ はともに $\theta$ で割り切れないため、 $\theta$ は非隣接条件を満たさないことになる。これは矛盾。 Q.E.D.

グランドプランによるFLTの証明. $p$ を奇素数とし、 $x, y, z$ を $x^p+y^p=z^p$ を満たすような整数とする。最終目標が達成されれば、補題１によって $x, y, z$ のうち少なくとも一つは無数の素数で割り切れることになる。それに耐え得る整数など $0$ しか存在しない。つまり、 $X^p+Y^p=Z^p$ は非自明な整数解を持ち得ない。 Q.E.D.

グランドプランの失敗

残念ながら、Sophie Germainは $p=3$ の時点で最終目標は破れることをLegendreへの手紙において自身で示してしまいました。それどころか後になって任意の奇素数 $p$ に対して非隣接条件を満たすような補助素数は有限個しか存在しないことが証明されています(Libri, Pellet, Dickson)。つまり、グランドプランは失敗に終わったのです。この記事では $p=3$ の場合の証明を紹介します。

補題２ $\theta=2np+1$ が奇素数 $p$ の補助素数であるとする。このとき、 $\bmod{\theta}$ における零でない $p$ 冪剰余の剰余類の個数は $2n$ 個である。

証明. $a$ を $1, 2, \dots, \theta-1=2np$ の中の一つとする。このとき、合同式 $x^p \equiv a \pmod{\theta}$ が整数解を持つための必要十分条件は $a^{2n}\equiv 1 \pmod{\theta}$ が成り立つことである。実際、 $x^p \equiv a \pmod{\theta}$ であれば

$a^{2n} \equiv (x^p)^{2n} = x^{\theta - 1} \equiv 1 \pmod{\theta}$

と計算できる。逆に $a^{2n} \equiv 1 \pmod{\theta}$ であるとしよう。 $a=1$ のときは自明なので $a \neq 1$ とする。 $r$ を $\bmod{\theta}$ に関する原始根とする*2。このとき、或る整数 $k\neq 0$ が存在して $a\equiv r^k \pmod{\theta}$ と書けるので、 $r^{2nk} \equiv 1 \pmod{p}$ となる。よって、 $\theta-1 \mid 2nk$ であり $k$ は $p$ の倍数であることがわかる。つまり、 $x^p \equiv a \pmod{\theta}$ は解を持つことがわかった。このことによって、 $\bmod{\theta}$ における $p$ 冪剰余であるような $1, 2, \dots, 2np$ の個数は $a^{2n} \equiv 1 \pmod{\theta}$ を満たす $1 \leq a \leq 2np$ の個数に一致することがわかった。 $r$ を $\bmod{\theta}$ における原始根とすると、 $r^p, r^{2p}, \dots, r^{(2n-1)p}, r^{2np}$ が $2n$ 乗すると $\bmod{\theta}$ で $1$ と合同になる相異なる全ての剰余類になっているので、その個数は $2n$ 個であることがわかる。 Q.E.D.

定理 (Sophie Germain) グランドプランの最終目標は $p=3$ で破れる。より詳しく言うと、 $13$ より大きい $6n+1$ 型の素数は必ず、 $1, 2, \dots, 6n$ の中に隣接する立方剰余を含む。従って、 $3$ の補助素数であって非隣接条件を満たすものは $7, 13$ に限る。

証明. $\theta=6n+1$ を $13$ より大きい素数とし、 $1, 2, \dots, 6n$ の中に隣接する立方剰余(CR)を含まないと仮定して背理法で証明する。非立方剰余をNCRと表す。
更に $1, 2, \dots, 6n$ がCR, NCR, CRという並びも含まない場合. 補題２より $1, 2, \dots, 6n$ の中にCRは丁度 $2n$ 個存在する。CRとCRの"間"が $2n-1$ 個あるが、各"間"には少なくとも二つのNCRがあるので $(2n-1)\times 2=4n-2$ 個のNCRが必要である。実際には $6n-2n=4n$ 個のNCRが存在するので、残り2個のNCRはどこかの"間"に分布することになる。可能性としては

三つのNCRを挟むような"間"が二つある
四つのNCRを挟むような"間"が一つだけある

のいずれかの状況になる(両端は必ずCR)。

さて、 $\theta > 13$ なので $1$ と $8$ は必ずCRである。仮定により $2, 3$ はNCR。 $4$ もNCRである。何故ならば、もし $4$ がCRであれば $8\times 4^{-1} \equiv 2$ もCRとなってしまうからである。そして、 $5$ はCRである。何故ならば、もし $5$ がNCRであれば、 $6$ は絶対にCR(NCRが5連続することはない)。すると、二つのCRである $6$ と $8$ の間にNCRになり得る数が $7$ しか存在せず、 $CR, NCR, CR$ という並びになって仮定に矛盾するからである。つまり、

$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
CR	NCR	NCR	NCR	CR	NCR	NCR	CR

となっており、先ほどの二つの可能性における1.の状況になっていることがわかった。また、自明の事実として、CRは $1, 2, \dots, 6n$ において対称に分布するので、CRは

$1, 5, 8, 11, \dots, 6n-10, 6n-7, 6n-4, 6n$

となっている。特に、 $1$ と $6n$ 以外のCRは $3$ で割った余りが $2$ であることに注意。

$13$ より大きい最小の素数は $19$ であるが、既に見たように $19$ は非隣接条件を満たさない。よって、 $\theta \geq 31=6\cdot 5 +1$ のケースのみを考えればよい。このとき、 $3^3=27 < 6n$ はCRであるが、これは $3$ の倍数である。すなわち、矛盾が導かれた。

$1, 2, \dots, 6n$ がCR, NCR, CRという並びを含む場合. CR, NCR, CRという並びを一つとって、二つのCRのうち大きい方を $\alpha$ 、小さい方を $\beta$ とする。 $\alpha-\beta=2$ である。 $r$ を $\bmod{\theta}$ の原始根とする。 $2$ は背理法の仮定によりNCRなので或る整数 $k$ が存在して $2 \equiv r^{3k \pm 1} \pmod{\theta}$ −①であることに注意。