James IvoryとEulerの定理

この記事ではEulerのトーシェント関数に関するEulerの定理にまつわる最近知った話を紹介します*1。

Eulerのトーシェント関数 $\varphi(n)$ は当ブログでは次の記事で初めて扱いました：

integers.hatenablog.com

2016年の初めに $2016$ という数の面白い性質がないかと探していたときに $\varphi(6102)=2016$ が成り立つことを知り( $6102$ は $2016$ をひっくり返したもの)、当時まだEulerのトーシェント関数を扱っていなかったためについでに定義を紹介しました。

そこでは、基本的な性質である $\varphi(n)$ の明示公式を紹介し、また何故「トーシェント」という聞きなれない用語を使うのかということについても述べています。

しかしながら、トーシェント関数に関する極めて基本的な合同式であるEulerの定理については紹介していませんでした。

Eulerの定理 $n$ を $2$ 以上の整数とし、 $a$ を $n$ と互いに素な整数とする。このとき、

$a^{\varphi(n)}\equiv 1 \pmod{n}$

が成り立つ。

それでも

integers.hatenablog.com

などでは有名事実として用いていました。当ブログでやっと証明を紹介したのが、Eulerの定理の精密化であるCarmichaelの定理に関する記事

integers.hatenablog.com

です。ですが、そこでの証明の紹介の仕方は

このブログでは多分これらの定理の証明をしたことはないのですが、Lagrangeの定理から自明です(Q.E.D.)。

という雑なものでした(「これら」はFermatの小定理も含めての意味)。この内容をもっと丁寧に解説したものとしてはtsujimotterさんの記事

tsujimotter.hatenablog.com

があります。

Eulerの定理は初等整数論(特に合同式)において威力を発揮する強力な定理であり、「Eulerの定理」という名前まで与えられている有名事実ですが*2、群論の立場に立ってしまうとLagrangeの定理を $(\mathbb{Z}/n\mathbb{Z})^{\times}$ という特別な群に適用しているに過ぎないことがわかります。

これは「理論を一般化すると自明に証明される」という数学でしばしば観測される現象の最もわかりやすい例の一つだと感じます。

このように群論的に自明なため当ブログでは証明を実質的に紹介していませんでしたが、群論の言葉を一切持ち出さずともEulerの定理は証明できます。Eulerの定理に限らず初等整数論には「代数学を整備すれば自明になるが初等整数論の範疇での証明も知られている」命題達が数多くあります。従って、初等整数論の教科書は代数学を整備するか初等整数論だけで貫き通すかの二種類に大別されます(折衷した教科書も多数あります)。

初等整数論を貫き通した教科書ではEulerの定理は大抵次のように証明されます:

Eulerの定理の証明.
$m_1, \dots, m_{\varphi(n)}$ を $n$ と互いに素な $n$ 以下の正整数全体とする。 $a$ を $n$ と互いに素な整数とするとき、 $am_1, \dots, am_{\varphi(n)}$ は $\bmod{n}$ で相異なる。
理由: $am_i \equiv am_j \pmod{n}$ であれば、 $a$ と $n$ が互いに素であることから $m_i \equiv m_j \pmod{n}$ となって $i=j$ が従う。
よって、集合として

$\{m_1 \bmod{n}, \dots, m_{\varphi(n)} \bmod{n}\}=\{am_1 \bmod{n}, \dots, am_{\varphi(n)} \bmod{n}\}$

が成り立ち、特に

$\displaystyle \prod_{i=1}^{\varphi(n)}m_i \equiv \prod_{i=1}^{\varphi(n)}am_i=a^{\varphi(n)}\prod_{i=1}^{\varphi(n)}m_i \pmod{n}$

を得る。 $\prod_{i=1}^{\varphi(n)}m_i$ は $a$ と互いに素なので、両辺をこの積で割ることができ、

$a^{\varphi(n)}\equiv 1 \pmod{n}$

が示された。 Q.E.D.

群論的に自明であることを学んだ後だと「Eulerの定理は自明」という印象が強く残ってしまいますが、この証明を始めて見たときのことを思い出すと当時の私(高校生のとき)はとても感動していました。再度鑑賞してみると中々の証明美を有している気がします。

さて、本記事の主題は何かというと、「この証明は誰が発見したのか」です*3。

実はEulerではありません。Eulerの定理はFermatの小定理*4

Fermatの小定理 $p$ を素数、 $a$ を $p$ と互いに素な整数とする。このとき、

$a^{p-1}\equiv 1 \pmod{p}$

が成り立つ。

の一般化です( $\varphi(p)=p-1$ )。これはFermatが1640年に言明していますが、例によって例のごとく証明は発表していません。そして、Eulerが1736年にFermatの小定理を証明した論文を執筆しています(実は同じ証明が1683年までにLeibnizによって得られていたようです)。

L. Euler, Theorematum quorundam ad numeros primos spectantium demonstratio, Commentarii academiae scientiarum Petropolitanae, 8 (1736/1741), 141–146.

Eulerの記号通りではないですが、まず $a=2$ の場合に

$\displaystyle (1+1)^{p-1}=\sum_{i=0}^{p-1}\binom{p-1}{i}$

より

$\displaystyle 2^{p-1}-1=\sum_{j=1}^{\frac{p-1}{2}}\left\{\binom{p-1}{2j-1}+\binom{p-1}{2j}\right\}=\sum_{j=1}^{\frac{p-1}{2}}\binom{p}{2j}$

と変形できて、 $2^{p-1}\equiv 1 \pmod{p}$ を示しています。次に

$\displaystyle 3^p=(1+2)^p=\sum_{i=0}^{p}\binom{p}{i}2^i$

より

$\displaystyle (3^p-3)-(2^p-2)=3^p-2^p-1=\sum_{i=1}^{p-1}\binom{p}{i}2^i$

が $p$ の倍数であることが従い、 $2^p-2$ が $p$ の倍数であることが既に示されているため、 $3^p-3$ も $p$ で割り切れることがわかります。そして、同様にして $a^p-a$ が $p$ で割り切れることを仮定すれば $(a+1)^p-a-1$ も $p$ で割り切れることを示すことができるので、帰納法によってFermatの小定理が得られるということが書かれています。

その後、Eulerは更に二つのFermatの小定理の証明を発表しており、

L. Euler, Theoremata arithmetica nova methodo demonstrata, Novi Commentarii academiae scientiarum Petropolitanae, 8 (1763), 74–104.

のTheorema 11においてEulerの定理が示されています。このEulerの定理のEuler自身による証明をフォローしたいところですが、まだ読めていません。

https://arxiv.org/pdf/1203.1993.pdf

にドイツ語翻訳があるため時間ができれば読みたいと思います。

さて、枠で囲ったEulerの定理の証明が誰のアイデアに基づくかという問題ですが、幾つかの文献によればその原型はイギリスの数学者James Ivory(1765/2/17 - 1842/9/21)によるそうです。

J. Ivory, Demonstration of a theorem respecting prime numbers, In T. Leybourn, editor, New Series of the Mathematical Repository, 264–266. Glendinning, London, 1806.

tsujimotterさんの記事にもあるようにこの証明法は当然Fermatの小定理の場合にも書き下すことができますが、もともとはFermatの小定理の新証明として発見されたものであり、そのままEulerの定理にも適用できるというわけです。

ただし、1801年には合同式を扱ったGaussのDAが公刊されているにもかかわらずIvoryの論文は合同式では書かれていません。Ivoryのアイデアが現代風の合同式を用いた記述として現れたのは、Dirichlet-Dedekindの書物"Vorlesungen über Zahlentheorie"とのことです。

James Ivoryという数学者の存在を知ったことが最近の小さなハッピーだったのでした。