フェルマーの小定理の証明

この記事では、フェルマーの小定理のさまざまな証明をまとめています。フェルマーの小定理とは、

a^{p}\equiv a{\pmod {p}}

すべての素数pとすべての整数aに対して(モジュラー算術を参照)。

簡略化

以下に示すフェルマーの小定理の証明のいくつかは、2つの簡略化に基づいている。

まず、 $a は$ $0 \leq a \leq p - 1$ の範囲にあると仮定できます。これはモジュラー演算の法則の単純な帰結です。つまり、まず $a を$ $p$ で割った余りを求めることができるということです。これは、 aをp で割った余りを求めることと矛盾しません。 $a^{p}$ 確認できるように、 $p$ を法として。

第二に、以下のことを証明すれば十分である。

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

$1 \leq$ $a$ $\leq$ $p$ $- 1$ の範囲の $a$ に対して。実際、このような $a$ に対して前の主張が成り立つ場合、両辺に $a$ を掛けると、定理の元の形式が得られます。

a^{p}\equiv a{\pmod {p}}

一方、 $a = 0$ の場合、この定理は自明に成り立つ。

組み合わせ論的証明

ネックレスを数えることで証明する

これはおそらく最も単純な証明であり、必要な数学的知識も最小限です。これは組み合わせ論的証明（複数の対象を2つの異なる方法で数える証明）の魅力的な例です。

ここで示されている証明は、ゴロンブの証明を改変したものである。^{[ 1 ]}

$話を単純にするために、 a は$ 正の整数であると仮定します。異なる記号のアルファベットを使用して、p 個の記号からなるすべての可能な文字列を考えます $。p$ 個の $位置$ それぞれに可能 $性$ が $ある$ ので、そのような文字列の総数は $a$ $p$ です(積の法則を参照)。

例えば、 $p = 5$ 、 $a = 2の場合、2 つの記号 ($ $A$ と $B$ など) を持つアルファベットを使用でき、長さ 5 の文字列は $25 = 32$ 通りあります。

AAAA

、

AAAAB

、

AAABA

、

AAABB

、

AABAA

、

AABAB

、

AABBA

、

AABB

、

アバア

、

アババ

、

アババ

、

アバブ

、

アババ

、

アババ

、

アバ

、

アバ

、

バアア

、

バアバ

、

ババ

、

ババ

、

ババ

、

ババブ

、

ババ

、

ババ

、

BBAAA

、

BBAAB

、

BBABA

、

BBABB

、

BBAA

、

BBBA

、

BBBA

、

BBBB

。

以下で説明するように、リストから単一の記号からなる文字列（この例では $AAAAA$ と $BBBBB$ ）を取り除くと、残りの $a p - a$ 個の文字列はグループに分けられ、各グループにはちょうど $p$ 個の文字列が含まれます。したがって、 $a p - a$ $はp$ で割り切れます。

ネックレス

それぞれの紐をネックレスに見立ててみましょう。つまり、紐の両端をつなぎ合わせ、一方の紐を回転させることでもう一方の紐が得られる場合、2本の紐を同じネックレスとみなします。この場合、2本の紐は「友達」であると言います。この例では、次の紐はすべて友達です。

AAAAB

、

AAABA

、

AABAA

、

ABAAA

、

BAAAA

。

以下に挙げるリストの各行は、それぞれ1本のネックレスに対応しており、リスト全体では32本の紐すべてが含まれています。

AAAAA

、

ああああ

、

ああああ

、

ああああ

、

ああああ

、

ああああ

、

AAABB

、

AABBA

、

ABBAA

、

BBAAA

、

BAAAB

、

アバブ

、

アババ

、

ババア

、

アバブ

、

バアバ

、

AABBB

、

ABBBA

、

BBBAA

、

BBAAB

、

BAABB

、

アバブ

、

ババ

、

アッバブ

、

バババ

、

ババブ

、

ABBBB

、

BBBBA

、

BBBAB

、

BBABB

、

BABBB

、

BBBBB

。

上記のリストでは、複数のシンボルを持つネックレスはそれぞれ5つの異なる文字列で表され、1つの文字列で表されるネックレスの数は2つ、つまり異なるシンボルの数であることに注意してください。したがって、このリストは $32 - 2が$ $5$ で割り切れる理由を非常に明確に示しています。

$与えられた文字列S$ が持つ友達の数を計算するには、次のルールを使用できます。

S が文字列

T

の複数のコピーで構成され、

T

自体がそれ以上繰り返し文字列に分解できない場合、

S

の友人の数(

S自体を含む) は

T

の長さに等しくなります。

例えば、文字列 $S = ABBABBABBABBから始めるとします。これは、より短い文字列$ $T = ABB$ を複数コピーして構成されています。これを一度に 1 つのシンボルずつ回転させると、次の 3 つの文字列が得られます。

ABBABBABBABB

、

BBABBABBABBA

、

ババババババ

。

$ABBは$ ちょうど3つの記号で構成されており、それ以上繰り返しの文字列に分解することはできないため、他に同様の文字列は存在しません。

証明の完成

上記の規則を用いると、フェルマーの小定理の証明を以下のように非常に簡単に完了できます。p個の文字列からなる初期プールは、 $次$ $の$ 2つのカテゴリに分けられます。

文字列の中には、 $p 個の同一の記号を含むものがあります。このような文字列はちょうど$ $個$ あり、アルファベットの各記号に 1 つずつ対応します。（今回の例では、文字列 $AAAAA$ と $BBBBB$ がこれに該当します。）
残りの文字列は、アルファベットから少なくとも2つの異なる記号を使用します。与えられた文字列 $Sを、ある文字列$ $T$ の繰り返しコピーに分割できる場合、 $T$ の長さは $S$ の長さを割り切る必要があります。しかし、 $S$ の長さは素数 $p$ であるため、 $Tの長さも$ $p$ しかありえません。したがって、上記のルールから、 $Sには（$ $S$ 自身を含めて）ちょうど $p個の$ 友達がいることがわかります。

2番目のカテゴリにはp − a個の文字列が含まれており $、それらは$ $p$ $個$ の文字列のグループに分けられ、各グループがネックレス1つに対応します。したがって、約束どおり、 $p - aは$ $p$ $で$ 割り切れなければなりません。

力学系を用いた証明

この証明では、力学系の基本的な概念をいくつか使用します。^{[ 2 ]}

まず、 n ≥ 2 は整数である関数族T _n ( x ) を考えます。この関数は、次の式によって区間[0, 1] をそれ自身に写像します。

T_{n}(x)={\begin{cases}\{nx\}&0\leq x<1,\\1&x=1,\end{cases}}

_ここで、 { y }はyの小数部分を表します。例えば、関数T3 ( x )は以下のように表されます。

数x _0は、f ( x ₀ ) = x ₀が成り立つ場合、関数f ( x )の不動点であると言われます。言い換えれば、f がx ₀を固定したままにする場合です。関数の不動点は、グラフを使って簡単に求めることができます。不動点は、f ( x )のグラフが直線y = xのグラフと交わる点のx座標です。たとえば、関数T ₃ ( x )の不動点は0、1/2、1 です。これらは次の図に黒丸で示されています。

以下の2つの補題が必要となります。

補題１．任意のn ≥ 2に対して、関数T _n ( x )はちょうどn個の不動点を持つ。

証明。上の図には、区間に対応する 3 つの固定点があります。 $[0,{\tfrac {1}{3}}),[{\tfrac {1}{3}}.{\tfrac {2}{3}}),[{\tfrac {2}{3}},1]$ $x$ についても同様であり、同じ幾何学的議論がすべての x に当てはまります。 $n\geq 2$ 。

補題2.任意の正の整数nとm、および任意の0 ≤ x ≤ 1に対して、

T_{m}(T_{n}(x))=T_{mn}(x).

言い換えれば、T _mn ( x ) はT _n ( x ) とT _m ( x )の合成です。

証明。この補題の証明は難しくないが、端点x = 1 には少し注意する必要がある。この点では、補題は明らかに正しい。

T_{m}(T_{n}(1))=T_{m}(1)=1=T_{mn}(1).

では、0 ≤ x < 1と仮定しましょう。この場合、

T_{n}(x)=\{nx\}<1,

したがって、T _m ( T _n ( x )) は次のように与えられる。

T_{m}(T_{n}(x))=\{m\{nx\}\}.

したがって、私たちが本当に示さなければならないのは

\{m\{nx\}\}=\{mnx\}.

そのためには、{ nx } = nx − kであることに注目します。ここで、kはnxの整数部分です。

\{m\{nx\}\}=\{mnx-mk\}=\{mnx\},

mkは整数なので。

それでは、関数T _{a ^p} ( x ) を調べることで、フェルマーの小定理の証明を本格的に始めましょう。a ≥ 2と仮定します。補題 1 から、この関数はa ^{p 個の}不動点を持つことがわかります。補題 2 から、

T_{a^{p}}(x)=\underbrace {T_{a}(T_{a}(\cdots T_{a}(x)\cdots ))} _{p{\text{ 回}}},

したがって、 T _a ( x )の任意の不動点は、自動的にT _{a ^p} ( x )の不動点になります。

我々は、 T _{a ^p} ( x )の固定点であって、T _a ( x )の固定点ではないものに興味がある。そのような点の集合をSと呼ぶことにしよう。補題 1 により、T _a ( x ) はちょうどa個の固定点を持つので、 Sにはa ^p − a個の点がある。次の図は、 a = 3、p = 2の場合の状況を示している。黒丸はSの点であり、その数は 3 ² − 3 = 6 個である。

証明の主なアイデアは、集合S をT _aの下での軌道に分割することです。これは、 S内の点x ₀を選び、それにT _a (x) を繰り返し適用して、点の列を得ることを意味します。

x_{0},T_{a}(x_{0}),T_{a}(T_{a}(x_{0})),T_{a}(T_{a}(T_{a}(x_{0}))),\ldots .

この数列はT _{a の}下でのx ₀の軌道と呼ばれます。補題 2 により、この数列は次のように書き換えることができます。

x_{0},T_{a}(x_{0}),T_{a^{2}}(x_{0}),T_{a^{3}}(x_{0}),\ldots .

x _{0 は}T _{a ^p} ( x )の固定点であると仮定すると、pステップ後にT _{a ^p} ( x ₀ ) = x ₀に到達し、その時点からシーケンスが繰り返されます。

しかし、数列はそれより早く繰り返されることはありません。もし繰り返されるとしたら、繰り返し部分の長さはpの約数でなければならず、1 でなければなりません ( pは素数なので)。しかし、これはx _0がT _aの固定点ではないという我々の仮定と矛盾します。

言い換えれば、軌道にはちょうどp 個の^異なる点が含まれています。これはSのすべての軌道について成り立ちます。したがって、 p − a個の点を含む集合Sは、それぞれp^個の点を含む軌道に分割できるため、p − aはpで割り切れます。

（この証明は、上記で示したネックレス数え上げの証明と本質的に同じですが、単に異なる視点から見ているだけです。区間[0, 1]は、基数aの数字の列で与えられると考えることができます（0と1の区別は、整数を「.0000...」で終わるものと「.9999...」で終わるものの区別に対応します）。T a _n^は、そのような列をn桁ずらすことに相当します。この固定点は、周期がnを割り切る巡回列になります。特に、T _{a ^p}の固定点は、長さpのネックレスと考えることができ、T _{a ⁿ}は、そのようなネックレスをnスポット回転させることに対応します。

この証明は、0と1を区別せずに、単に半開区間[0, 1)を用いるだけでも示すことができる。その場合、T _nはn − 1個の不動点しか持たないが、 T _{a ^p} − T _aは依然としてa ^p − aに収束し、必要な結果が得られる。

多項式証明

二項定理を用いた証明

証明１

オイラーによるこの証明[3]は、帰納^法^を^用いてすべての整数 $a \geq 0$ に対して定理を証明している。

基本ステップである $0 p \equiv 0 (mod p)$ は自明です。次に、定理が $a = kに対して真であれば、$ $a = k + 1$ に対しても真であることを示さなければなりません。この帰納的ステップには、次の補題が必要です。

補題。任意の整数 $x$ と $y$ および任意の素数 $p$ に対して、 $(x + y) p \equiv x p + y p (mod p)$ が成り立つ。

この補題は、新入生の夢のような例だ。証明は後回しにして、帰納法を進めよう。

証明。k ^p ≡ k (mod p ) と仮定し、( k + 1) ^pを考える。補題より、

(k+1)^{p}\equiv k^{p}+1^{p}{\pmod {p}}.

帰納法の仮定を用いると、k ^p ≡ k (mod p ) となり、自明なことに 1 ^p = 1 となる。したがって

(k+1)^{p}\equiv k+1{\pmod {p}},

これは、 a = k + 1の場合の定理の記述です。∎

補題を証明するために、任意の正の整数nに対して、次の二項定理を導入する必要があります。

(x+y)^{n}=\sum _{i=0}^{n}{n \choose i}x^{ni}y^{i},

ここで係数は二項係数であり、

{n \choose i}={\frac {n!}{i!(ni)!}},

階乗関数で表すと、n ! = 1×2×3×⋯× nとなります。

補題の証明。指数が素数pの場合の二項係数を考える。

{p \choose i}={\frac {p!}{i!(pi)!}}

二項係数はすべて整数です。分子は階乗の定義により因数pを含みます。0 < i < pの場合、分母のどちらの項もpの因数を含みません ( pの素数性に基づく)。したがって、係数自体が分子からpの素因数を持つことになります。

{p \choose i}\equiv 0{\pmod {p}},\qquad 0<i<p.

法pを用いると、素数pに対する二項定理の右辺の和のうち、最初と最後の項を除くすべての項が消去される。∎

pの素数性は補題に不可欠である。そうでなければ、次のような例が出てくる。

{4 \choose 2}=6,

これは4で割り切れません。

証明2

補題を用いると、次のようになる。

k^{p}\equiv ((k-1)+1)^{p}\equiv (k-1)^{p}+1\equiv ((k-2)+1)^{p}+1\equiv (k-2)^{p}+2\equiv \dots \equiv k{\pmod {p}}

。

多項式展開を用いた証明

証明は、最初にライプニッツによって発見され（彼はそれを公表しなかった）^{[ 4 ]} 、後にオイラーによって再発見された^{[ 3 ]。}これは、多項式の定理の非常に単純な応用であり、次のように述べている。

(x_{1}+x_{2}+\cdots +x_{m})^{n}=\sum _{k_{1},k_{2},\dots ,k_{m} \atop k_{1}+k_{2}+\dots +k_{m}=n}{n \choose k_{1},k_{2},\ldots ,k_{m}}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}

どこ

{n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!k_{2}!\dots k_{m}!}}

そして総和は、すべての $k$ $i$ の合計が $n$ となるような、非負の整数インデックス $k 1 、 k 2 、 ...、 k m$ のすべてのシーケンスについて取られます。

$したがって、 a を$ 1 の和として表すと、

a^{p}=(1+1+...+1)^{p}=\sum _{k_{1},k_{2},\dots ,k_{a} \atop k_{1}+k_{2}+\dots +k_{a}=p}{p \choose k_{1},k_{2},\ldots ,k_{a}}

明らかに、 $p$ が素数であり、任意の $j$ に対して $k j$ $がp$ と等しくない場合、次のようになります。

{p \choose k_{1},k_{2},\ldots ,k_{a}}\equiv 0{\pmod {p}},

そして、ある $jに対して$ $k j$ $がp$ に等しい場合、

{p \choose k_{1},k_{2},\ldots ,k_{a}}=1.

$k$ $j$ $=$ $p$ となる要素が $ちょうど$ $個$ 存在するので、定理が成り立つ。

（この証明は、先に述べたネックレス数え上げ証明の粗粒度版です。多項係数は、文字列を任意のアナグラムに並べ替える方法の数を数え、ネックレスの議論は、文字列を循環アナグラムに回転させる方法の数を数えます。つまり、ここで非自明な多項係数が $pで割り切れることは、長さ$ $pの非自明なネックレスを$ $p$ 通りの方法で文字列に展開できるという事実の結果と見なすことができます。）

この多項式展開は、もちろん、上記の二項定理に基づく証明の根底にあるものでもある。

べき積展開を用いた証明

形式的なべき積展開に基づく加法的組み合わせ論的証明は、ギエドリウス・アルカウスカスによって与えられた。^{[ 5 ]}この証明は、ユークリッドの互除法も二項定理も使用せず、有理係数を持つ形式的なべき級数を使用する。

オイラーの定理の特殊な場合としての証明

この証明^{[ 3 ]}^{[ 6 ]}は、ジェームズ・アイボリー^{[ 7 ]}によって発見され、ディリクレ^{[ 8 ]}によって再発見されたもので、モジュラー算術に関するある程度の予備知識を必要とする。

$aは正であり、$ $p$ で割り切れないと仮定しましょう。

数字の列を書き出すと、

そしてそれぞれを $p$ で割ると、結果として得られる数列は、

したがって、各数列の数値を掛け合わせると、結果は法 $p$ に関して同一になるはずです。

a\times 2a\times 3a\times \cdots \times (p-1)a\equiv 1\times 2\times 3\times \cdots \times (p-1){\pmod {p}}.

$用語$ をまとめると次のようになります

a^{p-1}(p-1)!\equiv (p-1)!{\pmod {p}}.

最後に、この等式の両辺から $1, 2, ..., p - 1$ を「消去」すると、次の式が得られます。

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

上記の証明には、正当化する必要のある2つのステップがあります。

数列 ( A ) の要素を法 $pで縮約したものが ($ B )の並べ替えである理由、そして
モジュラー演算において「約分」が有効な理由。

以下でこれらのことを証明しますが、まずはこの証明が実際にどのように機能するかの例を見てみましょう。

例

$a = 3$ かつ $p = 7$ の場合、問題の数列は次のようになります。

3,6,9,12,15,18;

7を法として還元すると

3,6,2,5,1,4,

これは単に

1,2,3,4,5,6.

これらを掛け合わせると

3\times 6\times 9\times 12\times 15\times 18\equiv 3\times 6\times 2\times 5\times 1\times 4\equiv 1\times 2\times 3\times 4\times 5\times 6{\pmod {7}};

つまり、

3^{6}(1\times 2\times 3\times 4\times 5\times 6)\equiv (1\times 2\times 3\times 4\times 5\times 6){\pmod {7}}.

1 × 2 × 3 × 4 × 5 × 6を約分すると、

3^{6}\equiv 1{\pmod {7}},

$これは、 a = 3$ および $p$ $=$ $7$ の場合のフェルマーの小定理です。

キャンセル法

まず、特定の状況下で「取り消し」が有効である理由を説明しましょう。正確な記述は次のとおりです。u $、$ $x$ 、 $y$ が整数であり、 $uが$ 素数 $p$ で割り切れず、かつ

$そうすれば、私たちはあなた$ から「キャンセル」して取得することができます

上記のフェルマーの小定理の証明でこの消去法則を使用したことは正当でした。なぜなら $、1、2、...、 p - 1の数は確かに$ $p$ で割り切れないからです(実際、それらは $p$ より小さいです)。

一般的に素数 $pが積$ $ab$ ( $a$ と $b$ は整数) を割り切るならば、 $p は$ $a$ または $b$ を割り切る、というユークリッドの補題を使えば、消去法則を簡単に証明できます。実際、主張 ( C )は、 $p が$ $ux$ $-$ $uy$ $=$ $u$ $($ $x$ $-$ $y$ $)$ を割り切ることを意味します。p $は$ $u を$ 割り切らない素数なので、ユークリッドの補題によれば、代わりに $x$ $-$ $y$ を割り切るはずです。つまり、( D ) が成り立ちます。

消去法則が成り立つ条件は非常に厳格であることに注意が必要です。これが、フェルマーの小定理が $p$ が素数であることを要求している理由です。例えば、 $2\times2 \equiv 2\times5 (mod 6)ですが、$ $2 \equiv 5 (mod 6)$ は成り立ちません。ただし、消去法則の次の一般化が成り立ちます。u 、 $x$ $、$ $y$ 、 $z$ が整数で、 $u$ と $zが$ 互いに素で、かつ

ux\equiv uy{\pmod {z}},

$そうすれば、私たちはあなた$ から「キャンセル」して取得することができます

x\equiv y{\pmod {z}}.

これはユークリッドの補題の一般化から導かれる。

再配置特性

最後に、このシーケンスがなぜ

a,2a,3a,\ldots ,(p-1)a,

pを法として還元すると、数列の並べ替えになります。

1,2,3,\ldots ,p-1.

まず、項 $a$ 、 $2 a$ 、 ...、 $(p - 1) aのいずれも$ $p$ を法として 0 と合同になることはありません。なぜなら、 $k$ $が1、 2、 ...、 p - 1$ のいずれかの数である場合、 $k は$ $p$ と互いに素であり、 $a も$ 同様であるため、ユークリッドの補題によれば $ka は$ $p$ と共通因数を持たないからです。したがって、少なくとも、数 $a$ 、 $2 a$ 、 ...、 $(p - 1) a を$ $p$ を法として簡約すると、 $1、 2、 3、 ...、 p - 1$ の数の中に必ず含まれることがわかります。

さらに、 $a$ 、 $2a$ 、...、 $(p - 1) aは、$ $p$ を法として簡約した後、 $すべて$ 異なる値でなければなりません。なぜなら、

ka\equiv ma{\pmod {p}},

ここで $k$ と $m$ $は1、2 、 ...、 p - 1$ のいずれかであり、消去法則によれば、

k\equiv m{\pmod {p}}.

$k$ と $mは$ $どちらも1$ から $p - 1$ の間にあるので、等しくなければなりません。したがって、項 $a$ 、 $2a 、$ ...、 $(p - 1) aを$ $p$ で割った余りは互いに異なる必要があります。まとめると、 $p - 1$ 個の数 $a$ 、 $2a 、$ ...、 $(p - 1) aを$ $p$ で割った余りは、数列 $1、2$ 、...、 $p$ $-$ $1の異なる要素になります。これらの数$ $は$ ちょうど $p$ $-$ $1個$ なので、前者が後者の並べ替えである可能性しかありません。

オイラーの定理への応用

この方法は、オイラーの定理を証明するためにも使用できます。ただし、 $1$ から $p -1$ までの数を、ある数 $m$ （必ずしも素数である必要はない）と互いに素で、かつpより小さい数に置き換えるというわずかな変更が必要です。並べ替えの性質と消去法則（上述の一般化された形式の下で）はどちらも満たされ、利用できます。

例えば、 $m = 10の場合、$ $m$ より小さく、 $m$ と互いに素な数は $1、3、7、9$ です。したがって、次の $よう$ $に$ なります $。$

a\times 3a\times 7a\times 9a\equiv 1\times 3\times 7\times 9{\pmod {10}}.

したがって、

{a^{\varphi (10)}}\equiv 1{\pmod {10}}.

オイラーの判定基準の系としての証明

群論を用いた証明

標準プルーフ

この証明^{[ 9 ]}は群論の最も基本的な要素を必要とする。

考え方は、集合 $G = {1, 2, ..., p - 1$ } に乗法（法 $p$ ）を加えると群を形成するという点を認識することです。検証に多少の努力が必要な唯一の群の公理は、 $G$ の各要素が可逆であるということです。とりあえずこれを前提として、 $a$ $は1 \leq a \leq p - 1 の$ 範囲にある、つまり $aは$ $G$ の要素であると仮定します。aの $位$ 数を $k$ とします。つまり、 $kは$ $a$ $k$ $\equiv$ $1$ $(mod$ $p$ $)$ となる最小の正の整数です。すると $、1,$ $a$ $,$ $a$ $2$ $, ...,$ $a$ $k$ $-1$ を法 $p$ で簡約したものは、位数が $k$ であるG $の$ 部分群を形成し、したがってラグランジュの定理により、 $kは$ $G$ の位数 $p$ $-$ $1$ を割り切ります。したがって、p $-$ $1$ $=$ $km$ $（$ ある正の整数 $m$ に対して）となり、

a^{p-1}\equiv a^{km}\equiv (a^{k})^{m}\equiv 1^{m}\equiv 1{\pmod {p}}.

$G$ のすべての要素 $b$ が可逆であることを証明するには、次のように進めます。まず、 $bは$ $p$ と互いに素です。したがって、ベズーの恒等式により、 $bx$ $+$ $py$ $=$ $1$ となる整数 $x$ と $y$ が存在します。この等式を法 $pで読むと、$ $bx$ $\equiv$ $1$ $(mod$ $p$ $)$ なので、 $x は$ $b$ の逆元であることがわかります。したがって、 $G$ のすべての要素は可逆です。つまり、先に述べたように、 $G$ は群です。

例えば、 $p = 11$ の場合、各要素の逆数は次のように与えられます。

オイラーの証明

前の証明を取り、ラグランジュの定理を使う代わりに、この特定の状況で証明しようとすると、オイラーの 3 番目の証明が得られます。これは彼がより自然だと感じたものです。^{[ 10 ]}^{[ 11 ]} $A を、要素が$ $p を$ 法とする数 $1、 a 、 a 2 、...、 a k - 1$ である集合とします。A $=$ $G$ $の$ 場合、 $k$ $=$ $p$ $-$ $1$ であり、したがって $k は$ $p$ $- 1$ を割り切ります。そうでない場合、何らかの $b$ $1$ $\in$ $G$ $\$ $A$ が存在します。

$A 1 を、$ $p$ を法とする数 $b 1 、 ab 1 、 a 2 b 1 、 ...、 a k - 1 b 1$ を要素とする集合とする。このとき、 $A$ $1は$ $k$ 個の異なる要素を持つ。そうでなければ、 $a$ $m$ $b$ $1$ $\equiv$ $a$ $n$ $b$ $1$ $(mod$ $p$ $)$ となるような異なる数 $m$ $、$ $n$ $\in$ ${0, 1, ...,$ $k$ $- 1$ }が 2 つ存在することになり、これは $a$ $m$ $\equiv$ $a$ $n$ $(mod$ $p$ $)$ となるので不可能である。一方、 $A$ $1のどの要素も$ $A$ の要素にはなり得ない。そうでなければ、 $a$ $m$ $b$ $1$ $\equiv$ $a$ $n$ $(mod$ $p$ $)となるような数$ $m$ $、$ $n$ $\in$ ${0, 1, ...,$ $k$ $-$ $1$ }が存在し、 $b$ $1$ $\equiv$ $a$ $n$ $a$ $k$ $-$ $m$ $\equiv$ $a$ $n$ $+$ $k$ $-$ $m$ $(mod$ $p$ $)となるが、これは$ $b$ $1$ $\notin$ $A$ なので不可能である。

したがって、集合 $A \cup A 1$ $には2 k 個の$ 要素があります。これがGと等しい場合、 $2$ $k$ $=$ $p$ $-1$ となり、したがって $k は$ $p$ $-1$ を割り切ります。そうでない場合は、何らかの $b$ $2$ $\in$ $G$ $\($ $A$ $\cup$ $A$ $1$ $)$ が存在し、要素が $b$ $2$ $、$ $ab$ $2$ $、$ $a$ $2$ $b$ $2$ $、 ...、$ $a$ $k$ $-$ $1$ $b$ $2$ を法 $pで簡約した集合として$ $A$ $2$ を定義することで、最初からやり直すことができます。 $G は$ 有限なので、このプロセスはどこかの時点で停止する必要があり、これにより $k が$ $p$ $-$ $1$ を割り切ることが証明されます。

例えば、 $a = 5$ かつ $p = 13$ の場合、

$52 = 25 \equiv 12 (mod 13)$ 、
$53 = 125 \equiv 8 (mod 13)$ 、
$54 = 625 \equiv 1 (mod 13)$ 、

$k = 4$ で $A = {1, 5, 8, 12$ }です。明らかに、 $A \neq G = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12$ } です。b 1 を G \ A の要素とします $。例えば$ $、 b 1$ = 2 と $します。すると$ 、

$2\times1 = 2$ 、
$2\times5 = 10$ 、
$2\times8 = 16 \equiv 3 (mod 13)$ 、
$2\times12 = 24 \equiv 11 (mod 13)$ 、

$A 1 = {2, 3, 10, 11$ }である。明らかに、 $A \cup A 1 \neq G$ である。b $2 を$ $G \( A ∪ A 1 )$ の要素とする。例えば、 $b 2 = 4$ とする。すると、

$4\times1 = 4$ 、
$4\times5 = 20 \equiv 7 (mod 13)$ 、
$4\times8 = 32 \equiv 6 (mod 13)$ 、
$4\times12 = 48 \equiv 9 (mod 13)$ 、

$A 2 = {4, 6, 7, 9$ }です。そして、 $G = A \cup A 1 \cup A 2$ です。

集合 $A$ 、 $A 1$ などは、実際には $G$ における $A$ の剰余類であることに注意してください。

注記

↑ Golomb, Solomon W. (1956), "フェルマーの「小」定理の組合せ論的証明" (PDF) , American Mathematical Monthly , 63 (10): 718, doi : 10.2307/2309563 , JSTOR 2309563
↑イガ、ケビン (2003)、「フェルマーの小定理の力学系による証明」、Mathematics Magazine、76 (1): 48–51、doi : 10.2307/3219132、JSTOR 3219132
1 2 3ディクソン、レナード・ユージン(2005) [1919]、「フェルマーとウィルソンの定理、一般化、および逆； $1、2、...、$ $p$ $-$ $1$ の法 $p$ の対称関数」、数論の歴史、第 I 巻、ドーバー、ISBN 978-0-486-44232-7、Zbl 1214.11001
↑ Vacca、Giovanni (1894)、「Intorno alla prima dimostrazione di un teorema di Fermat」、Bibliotheca Mathematica、第 2 シリーズ (イタリア語)、8 ( 2): 46–48
↑ Alkauskas, Giedrius (2009), "A Curious Proof of Fermat's Little Theorem", American Mathematical Monthly , 116 (4): 362–364 , arXiv : 0801.0805 , doi : 10.4169/193009709x470236 , JSTOR 40391097
↑ Hardy, GH ; Wright, EM (2008)、「フェルマーの定理とその帰結」、数論入門（第6版）、オックスフォード大学出版局、ISBN 978-0-19-921986-5
↑アイボリー、ジェームズ(1806)、「素数に関する定理の証明」、数学リポジトリ、新シリーズ、1 ( II): 6–8
↑ Lejeune Dirichlet、Peter Gustav ( 1828)、「Démonstrations nouvelles de quelques théorèmes relatifs aux nombres」、Journal für die reine und angewandte Mathematik (フランス語)、3 : 390–393
↑アンドレ・ヴェイユ; Rosenlicht、Maxwell (1979)、「§ VIII」、初心者向けの整数理論、Springer-Verlag、doi : 10.1007/978-1-4612-9957-8、ISBN 978-0-387-90381-1、Zbl 0405.10001
↑ Weil, André (2007) [1984], "§ III.VI", Number theory: An approach through history; from Hammurapi to Legendre , Birkhäuser , ISBN 978-0-8176-4565-6、Zbl 1149.01013
↑オイラー、レオンハルト(1761)、「Theoremata circa residua ex Divisione Potestatum relicta」(PDF)、Novi Commentarii Academiae Scientiarum Petropolitanae (ラテン語)、7 : 49–82

[1] Golomb, Solomon W. (1956), "フェルマーの「小」定理の組合せ論的証明" (PDF) , American Mathematical Monthly , 63 (10): 718, doi : 10.2307/2309563 , JSTOR 2309563

[2] イガ、ケビン (2003)、「フェルマーの小定理の力学系による証明」、Mathematics Magazine、76 (1): 48–51、doi : 10.2307/3219132、JSTOR 3219132

[Dickson-3] 1 2 3ディクソン、レナード・ユージン(2005) [1919]、「フェルマーとウィルソンの定理、一般化、および逆； $1、2、...、$ $p$ $-$ $1$ の法 $p$ の対称関数」、数論の歴史、第 I 巻、ドーバー、ISBN 978-0-486-44232-7、Zbl 1214.11001

[4] Vacca、Giovanni (1894)、「Intorno alla prima dimostrazione di un teorema di Fermat」、Bibliotheca Mathematica、第 2 シリーズ (イタリア語)、8 ( 2): 46–48

[5] Alkauskas, Giedrius (2009), "A Curious Proof of Fermat's Little Theorem", American Mathematical Monthly , 116 (4): 362–364 , arXiv : 0801.0805 , doi : 10.4169/193009709x470236 , JSTOR 40391097

[6] Hardy, GH ; Wright, EM (2008)、「フェルマーの定理とその帰結」、数論入門（第6版）、オックスフォード大学出版局、ISBN 978-0-19-921986-5

[7] アイボリー、ジェームズ(1806)、「素数に関する定理の証明」、数学リポジトリ、新シリーズ、1 ( II): 6–8

[8] Lejeune Dirichlet、Peter Gustav ( 1828)、「Démonstrations nouvelles de quelques théorèmes relatifs aux nombres」、Journal für die reine und angewandte Mathematik (フランス語)、3 : 390–393

[9] アンドレ・ヴェイユ; Rosenlicht、Maxwell (1979)、「§ VIII」、初心者向けの整数理論、Springer-Verlag、doi : 10.1007/978-1-4612-9957-8、ISBN 978-0-387-90381-1、Zbl 0405.10001

[10] Weil, André (2007) [1984], "§ III.VI", Number theory: An approach through history; from Hammurapi to Legendre , Birkhäuser , ISBN 978-0-8176-4565-6、Zbl 1149.01013

[11] オイラー、レオンハルト(1761)、「Theoremata circa residua ex Divisione Potestatum relicta」(PDF)、Novi Commentarii Academiae Scientiarum Petropolitanae (ラテン語)、7 : 49–82

[ 1 ]

[ 2 ]

法

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

簡略化