インテジャーズ

INTEGERS

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

Feit-Thompson予想

予想 (Feit-Thompson, 1962) p, qを相異なる素数とする。このとき、\displaystyle \frac{p^q-1}{p-1}\displaystyle \frac{q^p-1}{q-1}を割り切ることはない。

この予想はFeit-Thompsonの定理の文脈で、もし正しければその証明を簡略化できるだろうという形で提起されました。より強く\displaystyle \frac{p^q-1}{p-1}\displaystyle \frac{q^p-1}{q-1}は互いに素であるかという主張も考えられますが(これがFeit-Thompson予想と呼ばれることもある)、

N. Stephens, On the Feit–Thompson conjecture, Math. Comp., 25 (1971), 625.

において、こちらは否定されています。実際、p=17, q=3313とすると、

\begin{align} \frac{3313^{17}-1}{3313-1} &= 210704631469613851903863028967414811023076458348545820561 \\
&=112643\times 23946003637421\times 78115430278873040084455537747447422887\end{align}

ですが、4076桁の数\displaystyle \frac{17^{3313}-1}{17-1}112643で割り切れます。

James IvoryとEulerの定理

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

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

integers.hatenablog.com

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

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

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

Eulerの定理 n2以上の整数とし、anと互いに素な整数とする。このとき、
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以下の正整数全体とする。anと互いに素な整数とするとき、am_1, \dots, am_{\varphi(n)}\bmod{n}で相異なる。
理由: am_i \equiv am_j \pmod{n}であれば、anが互いに素であることから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_iaと互いに素なので、両辺をこの積で割ることができ、
a^{\varphi(n)}\equiv 1 \pmod{n}
が示された。 Q.E.D.

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

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

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

Fermatの小定理 pを素数、apと互いに素な整数とする。このとき、
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-2pの倍数であることが既に示されているため、3^p-3pで割り切れることがわかります。そして、同様にしてa^p-apで割り切れることを仮定すれば(a+1)^p-a-1pで割り切れることを示すことができるので、帰納法によって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という数学者の存在を知ったことが最近の小さなハッピーだったのでした。

Ivoryの定理

Ivoryの主要論文の一つがNewtonやLaplaceの定理に関する

J. Ivory, On the attraction of homogeneous ellipsoids, Phil. Trans. Royal Soc. London 99 (1809), 345–372.

のようですが、そこで次の定理を示しているそうです*5

Ivoryの定理 E_1, E_2を原点を中心とする\mathbb{R}^3内の共焦点楕円体とし、\alpha\alpha(E_1)=E_2なる線形変換とする。E_1上の二点P, Qをとるとき、線分の長さの等号
\overline{P\alpha(Q)}=\overline{\alpha(P)Q}
が成り立つ。

この定理は一般のn次元Euclid空間の場合も含め、様々な形で拡張されて研究されているようですが、二次元平面での主張は次のようになります:

共焦点であるような二つの楕円と二つの双曲線によって作られる四角形ABCDの対角線の長さは等しい。すなわち、AC=BDが成り立つ。

f:id:integers:20180702082421p:plain:w500

*1:学生のセミナー発表で知りました。

*2:とは言ってもEulerの業績が多すぎて「Eulerの定理」だけでは一意に定まりませんが。Wikipediaでは「オイラーの定理(数論)」、高校数学の美しい物語では「オイラーの定理(整数論)」と表現しています。

*3:精密な文献調査はまだ出来ていないため、簡単なまとめにとどめます。

*4:Fermatの大定理=Fermatの最終定理と比較して"小"という名前が付いていますが、英語にして省略するとどちらもFLTです。Fermat's little theoremとFermat's last theorem

*5:Ivoryの補題と呼んでいる文献もありました。

秋山・谷川アルゴリズム

アルゴリズム

まず、正整数の逆数を並べます。


\displaystyle 1 \quad \frac{1}{2} \quad \frac{1}{3} \quad \frac{1}{4} \quad \frac{1}{5} \quad \frac{1}{6} \quad \frac{1}{7} \quad \frac{1}{8} \quad \frac{1}{9} \quad \frac{1}{10} \quad \frac{1}{11} \quad \frac{1}{12} \quad \frac{1}{13} \quad \cdots


その後、ある計算規則に基づいて一行ずつ下に数列を追加していきます。その計算規則は

f:id:integers:20180611024202p:plain:w200

新しい数列の左から数えてN番目の数がCで、Cの上にある数がA, Bのとき、

C=N(A-B)

と計算されます。

この計算規則に基づいて得られる数列の一部分を見てみましょう:

f:id:integers:20180611022918p:plain

例えば、

f:id:integers:20180611170126p:plain

の部分は

\displaystyle \frac{5}{84}=6\left(\frac{3}{28}-\frac{7}{72}\right)

と計算されています。


さて、こうして得られた計算結果の一番左端に注目してみましょう。


f:id:integers:20180611025413p:plain


なんと、関-Bernoulli数になっています!!

integers.hatenablog.com


これが、秋山・谷川アルゴリズムです。

証明(by 金子先生)

数列\{b_{n,k}\}_{n, k\geq 0}b_{0, k}=\frac{1}{k+1}および漸化式

b_{n+1,k}=(k+1)(b_{n,k}-b_{n,k+1})

で定義するとき、b_{n,0}=B_nを示せばよい(B_nは関-Bernoulli数)。\displaystyle f_n(t):=\sum_{k=0}^{\infty}b_{n,k}t^kと母関数を作ると、漸化式よりn\geq 1のとき

\begin{align}f_n(t) &= \sum_{k=0}^{\infty}(k+1)(b_{n-1,k}-b_{n-1,k+1})t^k\\
&=\frac{\mathrm{d}}{\mathrm{d}t}\left(\sum_{k=0}^{\infty}b_{n-1,k}t^{k+1}\right)-\frac{\mathrm{d}}{\mathrm{d}t}\left(\sum_{k=0}^{\infty}b_{n-1,k+1}t^{k+1}\right)\\
&=\frac{\mathrm{d}}{\mathrm{d}t}\left(tf_{n-1}(t)\right)-\frac{\mathrm{d}}{\mathrm{d}t}\left(f_{n-1}(t)-b_{n-1,0}\right)\\
&=\frac{\mathrm{d}}{\mathrm{d}t}\left( (t-1)f_{n-1}(t)\right)\end{align}

が成り立つので、g_n(t):=(t-1)f_n(t)とおけば

\displaystyle g_n(t)=(t-1)\frac{\mathrm{d}}{\mathrm{d}t}(g_{n-1}(t) )

であり、

\displaystyle g_n(t)=\left( (t-1)\frac{\mathrm{d}}{\mathrm{d}t}\right)^ng_{0}(t)

を得る。Bell数の母関数表示と第二種Stirling数 - INTEGERSの補題1の第二種Stirling数に関する

\displaystyle \left(x\frac{\mathrm{d}}{\mathrm{d}x}\right)^n=\sum_{k=0}^n\left\{ {n \atop k}\right\}x^k\left(\frac{\mathrm{d}}{\mathrm{d}x}\right)^k

という公式があるので、x\mapsto t-1と変数変換して利用すれば

\displaystyle g_n(t) = \sum_{k=0}^n\left\{ {n\atop k}\right\}(t-1)^k\left(\frac{\mathrm{d}}{\mathrm{d}t}\right)^kg_0(t)

なる等式を得る。右辺の微分を実行してt=0を代入して-1倍すると、

\begin{align} b_{n,0}&=-\sum_{k=0}^n\left\{ {n\atop k}\right\}(-1)^kk!(b_{0,k-1}-b_{0,k})\\
&=\sum_{k=0}^n(-1)^kk!\left( (k+1)\left\{ {n \atop k+1}\right\}+\left\{ {n\atop k}\right\}\right)b_{0,k} \\
&=\sum_{k=0}^n(-1)^kk!\left\{ {n+1\atop k}\right\}b_{0,k}\\
&=\sum_{k=0}^n\frac{(-1)^kk!\left\{ {n+1 \atop k+1} \right\}}{k+1}\end{align}

が得られた。これは関-ベルヌーイ数の第二種Stirling数を用いた公式 - INTEGERSの(5)式より関-Bernoulli数に等しい。 Q.E.D.

最近、秋山・谷川アルゴリズムの広範な一般化が川﨑・大野によって得られています。