本記事の内容
本記事は「フェルマーの小定理」を証明する記事です。
本記事を読むにあたり、オイラーの\(\varphi\)関数について知っている必要があるため、以下の記事も合わせてご覧ください。
本記事の目標
目標は明確で、
です。
具体的には、以下の定理を証明することです。
フェルマーの小定理.
\(p\)が素数、\(x\in\mathbb{Z}\)ならば、次の1.および2.が成り立つ。- \(x\in\mathbb{Z}\)、\(x\not\equiv0\ ({\rm mod}\ p)\)ならば、\(x^{p-1}\equiv1\ ({\rm mod}\ p)\)である。
- \(x\in\mathbb{Z}\)ならば、\(x^p\equiv x\ ({\rm mod}\ p)\)である。
(※読み飛ばしてOK) フェルマーの「小」定理に関するちょっとした歴史
フェルマーといえば、フェルマーの最終定理が最も有名でしょう。
さらにこの定理は、問題提起から解決に至るまで実に約330年という年月を要したことを背景に、数学界隈だけなく世間一般に有名でしょう。
参考までに、フェルマーの最終定理はどんな定理かというと、
という定理です。
厳密に書けば
フェルマーの最終定理
\(n\geq3\)なる任意の自然数に対して、\(x^n+y^n=z^n\)を満たす\((x,y,z)\in\mathbb{N}^3\)は存在しない。です。
この定理が提起(というとちょっと違うけど)されたのは、実に1600年代です。
その約330年後の1995年にアメリカの数学者アンドリュー・ワイルズが証明を完了しました。
問題提起をしたフェルマーはフランスの裁判官でした。
フェルマーは法律家としての職務の傍ら、数学の研究を趣味としていました。
そんなフェルマーは古代ギリシアの数学者ディオファントスの著作『算術』を読み、本文中の記述に関連した着想を得ると、それを余白に書き残しておくという習慣を持っていました。
その「メモ」は数学的な定理やら予想やらだったわけですが、余白が限られていたためしばしば証明は省略されています。
面倒だったのか、余白な十分でも証明を省略する場合がありました。
今回解説するフェルマーの小定理もその一つで、実際に証明したのは微積分学の創始者の一人として有名なライプニッツです。
書き込みは48箇所におよびました。
この書き込みが知られるようになったのは、フェルマー没後の1670年にフェルマーの息子によってフェルマーの書き込み入の『算術』が刊行されてからの話です。
フェルマーの最終定理の逸話として有名なのは次の書き込みでしょう。
立法数を2つの立法数に分けることはできない。\(4\)乗\(\)を2つの\(4\)定数の和に分けることはできない。一般に、ベキが\(2\)より大きいとき、そのベキ定数を2つのベキ定数の和に分けることはできない。この定理に関して、私は真にに驚くべき証明を見つけたが、この余白はそれを書くには狭すぎる。
アンドリュー・ワイルズの証明はそれこそ「ここに書ききれないほど」膨大でした。
提示者フェルマーの「真に驚くべき証明」はもはや知ることができないのが実に残念です。
実は、フェルマーの最終定理については、日本人数学者も関わっています。
それが望月新一という数学者です。
彼はとてつもない天才で(そもそも数学者の時点ですごく賢い)、ABC予想を解決した数学者です。
このABC予想を仮定すれば、なんとフェルマーの最終定理は系として、証明が数行で終わるようです。
余談ですが、フェルマーについてお知りになりたければ、ピエール・ド・フェルマーを参照してください。
数学者の人生は結構面白いです(クセが強い人がおおい)。
(※順番に読まなくてOK) フェルマーの小定理を証明するために必要な諸定理集
先に申し上げておきますが、
です。
適宜、フェルマーの小定理中にリンクを貼り付けるので、その際にこの節に戻ってくれば十分です。
その１：合同式についての事実
命題1.
\(a,b\in\mathbb{Z}\)、\(a,b\neq0\)で、\(\gcd(a,b)=1\)であるとする。このとき、次の1.、2.及び3.が成り立つ。- \(bc\equiv1\ ({\rm mod}\ a)\)なる\(c\in\mathbb{Z}\)が存在する。
- \(x,y\in\mathbb{Z}\)で、\(bx\equiv by\ ({\rm mod}\ a)\)ならば、\(x\equiv y\ ({\rm mod}\ a)\)である。特に、\(bx\equiv0\ ({\rm mod}\ a)\)ならば、\(x\equiv 0\ ({\rm mod}\ a)\)である。
- \(d\in\mathbb{Z}\)に対して、\(\gcd(a,d)=1\)ならば、\(\gcd(bd,a)=1\)である。
命題1.の証明
なんてことありません。
1.の証明
次の事実を使います。
定理2.
一次の不定方程式 $$ ax+by+cz=k\quad (a,b,c,k\in\mathbb{Z}) $$ が整数解を持つための必要十分条件は、\(k\)が\(d=\gcd(a,b,c)\)で割り切れることである(変数の数は任意)。定理2.の証明は【代数学の基礎シリーズ】初等整数論編 その6を御覧ください。
定理2.により、\(ax+by=1\)を満たすような\(x,y\in\mathbb{Z}\)が存在することが保証されています。
\(ax+by=1\)を式変形すると、\(by-1=-ax=a\cdot(-x)\)となるため、
$$
by\equiv1\ ({\rm mod}\ a)
$$
となります。
したがって、\(c\)として\(y\)を採用すればOKです。
2.の証明
1.で存在が保証された\(c\in\mathbb{Z}\)を取りましょう。
このとき、
\begin{eqnarray}
bx\equiv by\ ({\rm mod}\ a)&\Longleftrightarrow&1\cdot bx\equiv 1\cdot by\ ({\rm mod}\ a)\\
&\Longleftrightarrow&cbx\equiv cby\ ({\rm mod}\ a)\\
&\Longleftrightarrow&1\cdot x\equiv 1\cdot y\ ({\rm mod}\ a)\\
&\Longleftrightarrow&x\equiv y\ ({\rm mod}\ a)
\end{eqnarray}となります。
また、\(y=0\)ならば\(x\equiv0\ ({\rm mod}\ a)\)です。
3.の証明
1.により、
\begin{eqnarray}
&&bc\equiv1\ ({\rm mod}\ a)\\
&&de\equiv1\ ({\rm mod}\ a)
\end{eqnarray}
を満たすような\(c,e\in\mathbb{Z}\)が存在します。
すると、
\begin{eqnarray}
(bc)(de)\equiv\ ({\rm mod}\ a)&\Longleftrightarrow&(bd)(ce)\equiv1\ ({\rm mod}\ p)\\
\end{eqnarray}
です。
ということは、
$$
(\exists x\in\mathbb{Z})\ {\rm s.t.}\ (bd)(ce)=1+ax
$$
です。
すなわち、\((bd)(ce)-ax=1\)です。
ここで、再度定理2.を用いることで、\(\gcd(a,bd)=1\)が得られます。
命題1.の証明終わり
その２：オイラーの\(\varphi\)関数と合同式
これは、「〇〇の定理」のような名前はついていない(と思いますが…)のですが、整数論において重要な定理です。
定理3.
\(m>1\)を整数とする。\(a\in\mathbb{Z}\)が\(\gcd(a,m)=1\)ならば、 $$ a^{\varphi(m)}\equiv1\ ({\rm mod}\ m) $$ である。ただし、\(\varphi\)はオイラーの\(\varphi\)関数である。証明の前に、「ざっくりオイラーの\(\varphi\)関数の復習をしたいな」という方は以下のを参照してください。
オイラーの\(\varphi\)関数のざっくり復習
ざっくり言えば\(n\)以下の自然数に対し、\(n\)と互いに素な整数の個数を対応させる関数\(\varphi:\mathbb{N}\longrightarrow \mathbb{N}\)をオイラーの\(\varphi\)関数と呼ぶのでした。オイラーの\(\varphi\)関数
関数\(\varphi:\mathbb{N}\longrightarrow \mathbb{N}\)を、\(n\in\mathbb{N}\)に対して定理3.の証明
\(S=\left\{ x_1,x_2,\cdots,x_{\varphi(m)}\right\}\)を\(1,2,\cdots,m-1\)の中で、\(m\)と互いに素であるもの全てを集めてきたものとします。
すると、\(S\)は完全被約剰余系です。
ここで、完全被約剰余系とは以下です。
(関連する概念として完全剰余系も復習として記載します)
完全剰余系、完全被約剰余系
\(m>1\)を整数とし、\(S\subset\mathbb{Z}\)とする。- 任意の整数が\(S\)の唯一の要素と\(m\)を法として合同となるとき、\(S\)を\(m\)をを法とする完全剰余系という。
- \(S\)の要素が全て\(m\)と互いに素であり、また\(m\)と互いに疎な任意の整数が\(S\)の唯一の要素と\(m\)を法として合同となるとき、\(S\)を\(m\)を法とする完全被約剰余系という。
さて、命題1.の3.により、\(ax_i\)も\(m\)と互いに素、すなわち\(\gcd(ax_i,m)=1\)です。
故に、
$$
ax_i\equiv x_j\ ({\rm mod}\ m)
$$
となる\(j\)が唯一つ存在します(暗に定理2.を使っていることに注意)。
この\(j\)を\(f(j)\)と書くことにしましょう。
\(ax_i\equiv ax_{i^\prime}\ ({\rm mod}\ m)\)であれば、命題1.の2.から、\(x_i\equiv x_{i^\prime}\ ({\rm mod}\ m)\)となります。
すなわち、今回の場合は\(S\)の中で考えているため、\(x_i=x_{i^\prime}\)が成り立ちます。
したがって、\(f:S\longrightarrow S\)は単射です。
さらには、\(\left| f(S)\right|=\left| S\right|\)です。
\(S\)は有限集合ですので、\(S\setminus f(S)=\emptyset\)でなければなりません。
したがって、\(f\)は全単射です(しっかり一対一対応している)。
故に、
$$
a^{\varphi(m)}x_1\cdots x_{\varphi(m)}\equiv \left( ax_1\right)\cdots\left( ax_{\varphi(m)}\right)\equiv x_1\cdots x_{\varphi(m)}\ ({\rm mod}\ m)
$$
です。
ここで、命題1.の3.を繰り返し用いれば、\(x_1\cdots x_{\varphi(m)}\)も\(m\)と互いに素であることがわかります。
故に、命題1.の2.から、
$$
a^{\varphi(m)}\equiv1\ ({\rm mod}\ m)
$$
です。
定理3.の証明終わり
フェルマーの小定理の証明
では、ようやっと本題です。
ただ、フェルマーの小定理は定理3.の系として直ちに導かれます。
フェルマーの小定理を再掲します。
フェルマーの小定理.
\(p\)が素数、\(x\in\mathbb{Z}\)ならば、次の1.および2.が成り立つ。- \(x\in\mathbb{Z}\)、\(x\not\equiv0\ ({\rm mod}\ p)\)ならば、\(x^{p-1}\equiv1\ ({\rm mod}\ p)\)である。
- \(x\in\mathbb{Z}\)ならば、\(x^p\equiv x\ ({\rm mod}\ p)\)である。
フェルマーの小定理の証明
1.の証明
まず、オイラーの\(\varphi\)関数の性質を使います。
定理4.
\(\varphi:\mathbb{N}\longrightarrow\mathbb{N}\)をオイラーの\(\varphi\)関数、\(p\in\mathbb{N}\)を素数とする。このとき $$ \varphi(p)=p-1 $$ である。すなわち、\(p\)以下の自然数で、\(p\)と互いに素な自然数は\(p-1\)個存在する。定理4.の証明は【代数学の基礎シリーズ】初等整数論編 その16を御覧ください。
さて、定理4.から\(\varphi(p)=p-1\)です。
ここで、定理3.を使います。
定理3.における\(a\)を\(x\)、\(m\)を\(p\)とした場合が今回の状況です。
確かに、定理3.において\(\gcd(a,m)=1)\)ですから\(x\not\equiv0\ ({\rm mod}\ p)\)を満たしています。
したがって、\(x^{\varphi(p)}\equiv1\ ({\rm mod}\ p)\)が成り立つため、
$$
x^{p-1}\equiv1\ ({\rm mod}\ p)
$$
が成り立ちます。
2.の証明
1.により、\(x\not\equiv0\ ({\rm mod}\ p)\)ならば、\(x^{p-1}\equiv1\ ({\rm mod}\ p)\)です。
\(x\equiv x\ ({\rm mod}\ p)\)ですから、
\begin{eqnarray}
x^{p-1}\equiv1\ ({\rm mod}\ p)&\Longleftrightarrow&x^{p-1}\cdot x\equiv 1\cdot x\ ({\rm mod}\ p)\\
&\Longleftrightarrow&x^p\equiv x\ ({\rm mod}\ p)
\end{eqnarray}
となります。
特に、\(x=0\)なれば、\(x^p\equiv x\equiv0\ ({\rm mod}\ p)\)となります。
フェルマーの小定理の証明終わり
フェルマーの小定理の応用例(さらっと。詳しくは次回)
フェルマーの小定理は応用が多岐にわたるため、初等整数論において非常に重要な位置にあります。
その最たる例が暗号理論です。
RSA暗号については以前、さらっと解説しています(【代数学の基礎シリーズ】初等整数論編 その8)。
次回はフェルマーの小定理を知っているという前提で実際にどのように暗号に応用されているかということを紹介します。
皆様のコメントをください！
まだ梅雨は明けていないようですが、暑い日が続いていますね。
筆者は毎日電車で通勤していますが、満員電車ということもあり非常に暑いです。
会社につく頃には背中がすでに汗でびちゃびちゃです。
夏の満員電車を乗り切る汗や暑さに対するアイテムを教えてください(切実)。
結
今回は、フェルマーの小定理を証明しました。
フェルマーの小定理は初等整数論の中で非常に重要な定理です。
なぜならば、応用例が多岐にわたるからです。
最たる例は暗号への応用だと思います。
我々の個人情報がインターネット上で保護されているのは、整数論が背景にあるのです。
次回は、フェルマーの小定理がどのように暗号に応用されているかについて紹介します。
乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
初等整数論について、以下の書籍をオススメします！
コメントをする