「二つの平方数の和」による素数判定法について

ある数が二つまたはそれ以上の異なる方法によって二つの平方数に分割しうるとき, それは素数でなく, 二つ以上の因子の合成である.

(L. Euler, 1749)

この記事では, 以下を目標として上記の定理を証明します.

「二つの平方数の和」に関する諸定理を応用し, 五桁の数 $\ 10001\$ が素数でないことを証明する.

前提知識

素数, 平方数, 二次不等式

数学史から
命題 E.7 の証明
10001 が素数でないこと
参考文献

数学史から

「数論の父」として知られているかのフェルマ Fermat は, 裁判官の職に就きながらも数学, 取りわけ「数の理論」の研究に注力し, 現代の数学にも通ずる幾つもの定理を発見しました. フェルマは数の世界を渡りながら多くの現象を観察しましたが, その証明については稀に概論を書きとめているのみで, 殆ど全ての場合において証明を遺しませんでした. フェルマの発見に関心を寄せて, 彼の理論を補完するべく証明を試みたのは, オイラー Euler やガウス Gauss を始めとする後世の数学者たちでありました.

中でもフェルマが気に入っていた発見は, 彼が直角三角形の基本定理 la proposition fondamentale des triangles rectangles と名づけた定理で, これは現今フェルマの二平方和の定理と呼ばれている命題に当ります. フェルマは往々にして直角三角形の基本定理を語り, パスカル Pascal やフレニクル Frenicle など多くの数学者に手紙を送って報告しました. その定理の内容は, $\ 4\$ の倍数よりも $\ 1\$ だけ大きい素数は, 何れも二つの平方数の和に表されるというもので, 例えば $\ 5,\$ $13,\$ $17,\$ $29\$ であれば

\begin{align} 5=1+4,\ 13=4+9,\ 17=1+16,\ 29=4+25 \end{align}

という平方数の和のことを意味します. フェルマは生涯を通してこの定理に関する研究を進め, ある正の整数が, 何通りの方法によって二つの平方数の和に書かれるのかという問いを主題としていました.

直角三角形の基本定理に対して的確な証明を与えた人物はフェルマ自身でなかったことは, 非常に有名であると思います. 彼の書きのこしには大変な論理の欠陥があって, 初めて正しい証明が記述されたのはオイラーやガウスの時代であります. 次の画像は, オイラーが一七五八年にベテルブルク新紀要にて発表した論文『二つの平方数の和であるような数について』の中で, 直角三角形の基本定理を取りあげているところです.

Prōpositiō V. §28. Omnis numerus prīmus, quī sunt ūnitāte excēdit multiplum quaternariī, est summa duōrum quadrātōrum.

「命題 5. セクション 28. 四の倍数を一だけ超える全ての素数は, 二つの平方数の和である. 」

Prōpositiō VI. §35. Sī numerus formae $\ 4n+1\$ ūnicō modō in duo quadrāta inter sē prīma resoluī queat, tum certē est numerus prīmus.

「命題 6. セクション 35. $\ 4n+1\$ 型の数がただ一通りの方法によって互いに素な二つの平方数に分割しうるならば, そのとき (その数は)

必ず素数である. 」

Prōpositiō VII. §40. Quī numerus duōbus plūribusve dīversīs modīs in duo quadrāta resoluī potest, ille nōn est prīmus, sed ex duōbus ad minimum factōribus conpositus.

「命題 7. セクション 40. 数が二つまたはそれ以上の異なる方法によって二つの平方数に分割しうるとき, それは素数でなく, 少なくとも二つの因子の合成である. 」

以上の通りに, オイラーは「 $4n+1\$ 型の素数が少なくとも一通りの方法によって二つの平方数の和として書かれる」という命題に加えて, 「ある数を二つの平方数の和に分ける方法が一通りのみであることと, その数が素数であることは同値である」ことを記述しています. 然しながらこの論文におけるオイラーの議論には小さな欠陥があって, 究極の解決には至らないで終わってしまいます. フェルマの考察も交えた証明の完成版は, 一八〇一年にガウスの出版した『ディスクウィシティオネス』"Disquisitiones Arithmeticae" (整数論の考究) に収録されています.

その後の「数の理論」はアーベル Abel, ヤコビ Jacobi, ディレクレ Dirichlet, クンマー Kummer, デデキント Dedekind を始めとする一九世紀の数学者に引きつがれて, フェルマに始まりガウスが整備した直角三角形の基本定理についての一連の研究は, 平方剰余の理論, 延いては二次体の整数論, 類体論へと「算術学」が急進してゆく契機となったのであります.

オイラーは自身の研究の応用として, $\ 1000009$ (百万九) は素数であるか否かという問題を考察しています. 今回の記事で取りあつかうのは, 上記のオイラーの論文にある命題 7 の証明と, オイラーの用いた「二つの平方数の和」による素数判定法のお話になります.

命題 E.7 の証明

以下, あらゆる $\ 4n+1\$ 型の素数が (少なくとも一通りの方法で) 二つの平方数の和の形に書かれるというオイラーの命題 5 を仮定します. 証明の一つは当ブログの過去の記事にも紹介がありますので, 興味の有られる方は是非ともご一読ください.

yu200489144.hatenablog.com

本来であれば命題 6 の証明も述べるべきでありますが, それには平方剰余の第一補充則 (上の記事の中に説明があります) と呼ばれる定理が必要になります. 故に, ここでは部分的な次の命題だけを証明することにします.

命題 E.6-1. $\ 4n+1\$ 型の異なる二つの素数の積である数は, 和の順序を除いても, 必ず二通りまたはそれ以上の方法によって二つの平方数の和に表される.

証明. 二つの $\ 4n+1\$ 型の素数を $\ p,\ q\$ とする. 二平方和定理 (命題 E.5) によって, \begin{align} &p=a^2+b^2,\quad q=c^2+d^2,\\ &a\gt b\gt 0,\quad c\gt d\gt 0,\\&ad\geqslant bc \end{align} を満たし, かつ $\ (a,b)\$ と $\ (c,d)\$ が互いに素である整数 $\ a,\ b,\$ $c,\ d\$ が存在する. 若し $\ ad=bc\$ であるならば, 最大公約数の仮定により $\ a=c\$ が得られて不合理であるので, $\ ad\gt bc\$ である. 二つの平方数の和に関する二つの等式 \begin{align} &(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2 \\&(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2 \end{align} が成りたつことを考えると, 積 $\ pq\$ は少なくとも一通りの方法によって二つの平方数の和に書かれる. 四つの数 $\ ac+bd,\$ $ad-bc,\$ $ac-bd,\$ $ad+bc\$ は何れも正であり, 大小について \begin{align} &ac+bd\gt ad+bc\gt ad-bc,\\ &ac+bd\gt ac-bd \end{align} の関係にあるから, 上記の等式における右辺の二平方和は異なる分割の方法を表す. 故に, 積 $\ pq\$ は少なくとも二通りの方法によって二つの平方数の和に表される.

$\Box$

命題 E.7. ある数が (和の順序を除いて) 二つまたはそれ以上の異なる方法によって二つの平方数の和として書かれるとき, それは素数でなく, 二つ以上の $\ 1\$ でない正の因子の合成である.

証明. ある素数 $\ p\$ が, 二つの平方数の和として二通りに表されると仮定して, \begin{align} &p=a^2+b^2=c^2+d^2,\\ &a\geqslant b\geqslant 0,\quad c\geqslant d\geqslant 0,\quad a\gt c \end{align} と定める. この仮定の下で $\ a^2c^2-b^2d^2\$ なる整数を考えると, これは $\ p\$ の倍数であり*1, 従って $\ ac\pm bd\$ の何れか少なくとも一方は $\ p\$ の倍数である. $\ p\$ の倍数である方の数を $\ ac+\epsilon bd\$ とすれば, 二平方和に関する等式

\begin{align} p^2=(a^2+b^2)(c^2+d^2)=(ac+\epsilon bd)^2+(ad-\epsilon bc)^2 \end{align}

において $\ (ac+\epsilon bd)^2\$ は $\ 0\$ または $\ p^2\$ に等しくなければならなず, そのとき $\ ac+\epsilon bd\$ と $\ ad-\epsilon bc\$ の何れかは $\ 0\$ に等しい. 故に $\ ac=bd\$ あるいは $\ ad=bc\$ が得られるのであるが, これらの結果は何れも始めに仮定した大小序列に矛盾する. 由って, ある整数 $\ p\$ が二つの平方数の和として二通りに表されるとき, $\ p\$ が素数であることは有りえない.

$\Box$

10001 が素数でないこと

先程, オイラーが直角三角形の基本定理の証明を発見し, その結果を $\ 4n+1\$ 型のある数が素数であるか否かという問題に適用したと述べました. 本項は, この素数判定に用いられた具体的手法の解説になります.

下の資料は, オイラーが一七七八年に著した論文『数 $\ 1000009\$ が素数であるか否かということが研究せられる』の冒頭とセクション 1 と 2 の部分です. こちらの論文は, 一七七五年にオイラーが発表した『百万までの素数表およびその続き. 全非素数の最小の約数を併記する』という素数表に誤って $\ 1000009\$ を記載してあったのを訂正する形で投稿されました.

図 4. 『数 $\ 1000009\$ が素数であるか否かということが研究せられる』.

Utrum hic numerus; $1000009$ ; sit prīmus, nec nē inquīritur.

(中略)

§1. Cum hic numerus manifēstō sit summa duōrum quadrātōrum, scīlicet: $1000^2+3^2$ , quaestiō hūc redit: num iste numerus adhūc aliō modō in duo quadrāta dīvidī queat? Sī enim id nūllō modō fierī potest, hic numerus certē erit prīmus; sīn autem adhūc aliō modō tālis resolutiō succēdat, tum nōn erit prīmus, atque tum adeō eius dīvīsōrēs assignāre licēbit. Quārē sī ūnum quadrātum statuāmus $=xx$ , inquīrendum est, utrum altera pars, scīlicet: $1000009-xx\$ ēvādere queat quadrātum, praeter casūs $x=3$ et $x=1000$ , id quod sequentī modō explōrārī poterit.

§2. Quoniam iste numerus definit in $9$ , alterum quadrātum necessāriō dīvidī poterit per $5$ , atque adeō per $25$ . Statuāmus igitur, haec formulam $1000009-xx$ esse dīvisibilem per $25$ , ac perspiciuum est, necessāriō esse dēbere $x=25a+3$ ; tum enim habitur haec formula: \begin{align} 1000000-6\cdot25a-25^2\cdot aa \end{align} quae dīvisa per $25$ abit in hanc: $40000-6a-25aa$ , quae ergō forma quadrātum esse dēbet.

「数 $\ 1000009\$ が素数であるか否かということが研究せられる」

(中略)

「セクション 1. この数は明らかに二つの平方数の和即ち $\ 1000^2+3^2\$ であり, 我々の疑問は『ならば, この数は他の方法によってまた二つの平方数に分割することができるか』という問いに到達する. 若し真にこれが如何なる方法によってもできなければ, この数は必ず素数であろうが, 然し他の方法によってまたそのような分解が達成されるならば, そのときは素数でなく, 加えてその約数を割りあてることが可能であろう. 平方数の一つを $\ =xx\$ と置くとき, 調べるべきことは, もう一方の部分即ち $\ 1000009-xx\$ が $\ x=3\$ と $\ x=1000\$ の場合を除いて平方数になりうるか否かということであり, そしてこれは, 次の方法によって実行することが可能となるであろう. 」

「セクション 2. この数は $\ 9\$ で終るがために, 一方の平方数は必然的に $\ 5\$ によって割りきれ, そして更に $\ 25\$ でも割りきれるであろう. ここで式 $\ 1000009-xx\$ を $\ 25\$ により割りきれる数と見なすならば, 自明に $\ x=25a+3\$ であることを必要とし (注), そのとき \begin{align} 1000000-6\cdot25a-25^2\cdot aa \end{align} の式が得られる. そしてこれは $\ 25\$ で割ることによって $\ 40000-6a-25aa\$ になり, 従ってこれが平方の形でなければならない. 」

(注) このとき $\ x\$ を $\ 25\$ で割った余りは $\ 3,\ 22\$ の何れかになりますが, $\ xx\$ を扱うに当って $\ x\$ の符号は正負何れでも構わないので, $\ x=25a+3\$ と書くことができます.

論文は全部で十一頁ページあり, セクション 3 以降にも証明が続いていますが, 全部の内容を追うとなると計算が大変になるので, 代わりに五桁の数 $\ 10001\$ が素数でないことを同じ方法によって証明してみせたいと思います.

命題 10001. 五桁の数 $\ 10001\$ は素数でない.

証明. この数は明らかに二つの平方数の和 $\ 100^2+1^2\$ であり, 考えるべきことは, この数が他の方法によってまた二つの平方数に分割されうるか否かということである. 若し真にこれが如何なる方法によっても不可能であればこの数は素数であるが, 他の方法によって分解が達成されるならば, そのときは合成数である. 平方数の一つを $\ x^2\$ と置くとき, 調べるべきことは, 残りの数 $\ 10001-x^2\$ が $\ x=100\$ と $\ x=1\$ との場合を除いて平方数になりうるか否かということである. この数は末尾が $\ 1\$ であるから, 一方の平方数は必ず $\ 5\$ によって割りきれ, そして $\ 25$ によっても割りきれる. 由って式 $\ 10001-x^2\$ が $\ 25\$ によって割りきれる方の数であるとすれば, $\ x\$ の符号を塩梅することによって $\ x=25a+1\$ なる整数 $\ a\$ を選ぶことができる. そのとき $\ 10001-x^2\$ は \begin{align} 10000-2\cdot25a+25^2a^2 \end{align} に等しく, これは $\ 25\$ で割ることによって $\ 400-2a-25a^2\$ となる. これが平方数でなければならない.

平方数は必ず非負であるから, $\ 10001-x^2\$ が平方数であるならば, 式 $\ 400-2a-25a^2\$ は非負である. 二次方程式 $\ 400-2A-25A^2=0\$ 即ち $\ (25A+1)^2=10001\$ の二つの解が \begin{align} A=\frac{-1\pm\sqrt{10001}}{25} \end{align} であることを考慮すれば, $\ 400-2a-25a^2\geqslant0\$ の不等式は $\ -4\leqslant a\leqslant 3\$ に置きかえられる. 故に $\ a\$ は $\ -4\$ 以上 $\ 3\$ 以下の整数でなければならない. これらの候補の各々に対応する $\ 400-2a-25a^2\$ の値を計算し, 平方数をまとめると次表の通りになる. \begin{align} \begin{array}{|r|l|}\hline a&400-2a-25a^2\\\hline -4&8\\ -3&181\\ -2&304\\ -1&377\\ 0&400=20^2\\ 1&373\\ 2&296\\ 3&169=13^2\\\hline \end{array}\end{align}

ここから $\ 10001-x^2\$ が平方数となるのは $\ x=1,\ 76\$ の二通りのみである. これらは実際の二平方和 \begin{align} 10001=1^2+100^2=76^2+65^2 \end{align} に対応する. かくして $\ 10001\$ は二通りの方法によって二つの平方数に分割される数であり, 従って合成数である.

$\Box$

証明 2.

\begin{align}10001=11025-1024=105^2-32^2=73\times137\end{align}

であるから, 合成数である.

$\Box$

この通りに, オイラーは専ら趣味の目的において素数の研究を進め, 十数頁にわたる計算を経由して, 七桁ある巨大な数が素数でないという事実を突きとめたのであります.

少し本題から逸れるのでありますが, 私が数学の歴史について興味を抱くようになり, オイラーが著したという数々の論文を探していたときは, 古典ともいわれるような数百年前の数学文が読めることを愉しく思い, 夜通しで文献を読みあさったことがありました. そのような偉大な論文の中に「数 $\ 1000009\$ が素数であるか否かが研究せられる」という風変わりな表題のものが一冊あり, 然もそれを開いてみると非常に高雅な文体で書かれてあって, 何か可笑しいように思っていましたら, 読んでいるうちに段々と眠気も差してくるもので, 長く続いた計算式を追うのに疲れ, 次の日に見かえしてみると, 殆どの内容について記憶が有りませんでした. そうしてはっきりとは解らないまま, 論文を片付けてしまったのだと思います.

整数論とは, 誠に退屈なあれこれの計算が, そのようにたいそう偉そうな文体を用いて書かれる変へん梃てこなもので, いつもどこかに数学者の可笑しさを伴っているのです.

数学史の流れとしては, オイラーが「 $1000009\$ は素数か否かの研究」を出したのちに, ルジャンドル, ガウスなどが新しい理論を継つぎ々つぎに大成し, $\ x^2+y^2\$ を始めとする二次形式の性質について長いあいだ研究をおこなってきました. 結局すると, 二平方和の真相が複素整数の性質を使って明快に論じられるようになったのは十九世紀に入ってから漸ようやくのことであって, フェルマが二平方和定理に気が付いてからオイラーが証明に取りくむまで百余年あり, それがガウスによって補完されるまでに更に五十年, 本質的な視点が提唱されるのにまた三十年, ...... 一つの物事を知るのに二百年も掛かるとは, 全く気の遠くなるような話しではありませんか. 常に, 数学の進歩というものがゆっくりであることを痛感させられる限りです.

参考文献

[1] 高瀬正仁 (2019), 『数論のはじまりフェルマからガウスへ (数学の泉) 』, 日本評論社.

以下, 括弧内には刊行年のみを記す.

[2][E228] L. Euler (1758), "De numeris, qui sunt aggregata duorum quadratorum." Novi commentarii academiae scientiarum Petropolitanae, Vol. 4; pp. 3-40.

[3][E467] L. Euler (1775), "De tabula numerorum primorum usque ad millionem et ultra continuanda, in qua simul omnium numerorum non primorum minimi divisores exprimantur." Novi commentarii academiae scientiarum Petropolitanae, Vol. 19; pp. 132-183.

[4][E699] L. Euler (1797), "Utrum hic numerus; $1000009$ ; sit primus, nec ne, inquiritur." Nova acta academiae scientiarum Petropolitanae, Vol. 10; pp. 63-73.

*1: $\ a^2c^2-b^2d^2\$ を $\ (a^2+b^2)(c^2+d^2)-(a^2+b^2)d^2-b^2(c^2+d^2)\$ のように変形すると, これは $\ p\$ の倍数の和.