フェルマーの小定理

数論において、フェルマーの小定理は、 $p が$ 素数ならば、任意の整数 $a$ に対して、数 $a p - a$ $はp$ の整数倍であると述べている。モジュラー算術の記法では、これは次のように表される。 $a^{p}\equiv a{\pmod {p}}.$

例えば、 $a = 2$ 、 $p = 7$ の場合、 $27 = 128$ となり、 $128 - 2 = 126 = 7 \times 18は$ $7$ の整数倍です。

$aが$ $p$ で割り切れない場合、つまり $aが$ $p$ と互いに素である場合、フェルマーの小定理は、 $a$ $p$ $- 1$ $- 1が$ $p$ の整数倍であるという記述と同等であり、記号で表すと次のようになります。^[¹^]^[²^] $a^{p-1}\equiv 1{\pmod {p}}.$

例えば、 $a = 2$ 、 $p = 7$ の場合、 $26 = 64$ となり、 $64 - 1 = 63 = 7 \times 9は$ $7$ の倍数です。

フェルマーの小定理はフェルマー素数判定法の基礎であり、初等整数論の基本的な結果の一つである。この定理は、1640年にそれを述べたピエール・ド・フェルマーにちなんで名付けられている。フェルマーの最終定理と区別するために「小定理」と呼ばれている。^{[ 3 ]}

歴史

ピエール・ド・フェルマーは、1640年10月18日付の友人であり腹心の友であるフレニクル・ド・ベシー宛の手紙の中で、この定理を初めて述べた。彼の定式化は、次の式と同等である。^{[ 3 ]}

$p$ が素数で、 $a が$ $p$ で割り切れない任意の整数である場合、 $a p - 1 - 1は$ $p$ で割り切れます。

フェルマーの当初の主張は

最高の品質を誇示します。 $-1$ 進行状況の進行状況、その他の説明は、最も重要な要素の 1 つ以上です。 $-1$ ; et, après qu'on a trouvé la première puissance quiSatisfait à la question, toutes celles dont les exposants Sont multiples de l'exposant de la première Satisfont tout de même à la question.

これは、理解を容易にするために括弧内に説明と数式を追加して、次のように翻訳できます。

すべての素数 [ $p$ ] は、任意の等比数列[ $a$ $,$ $a$ $2$ $,$ $a$ $3$ $, \dots ] のいずれかの$ べき乗から 1 を引いた数を必ず割り切ります[つまり、 $p が$ $a$ $t$ $- 1$ を割り切るような $t$ が存在します]。また、このべき乗の指数 [ $t$ ] は、与えられた素数から 1 を引いた数を割り切ります [ $p$ $- 1を割り切ります]。この条件を満たす最初のべき乗 [$ $t$ ]が見つかった後は、その指数の倍数であるすべてのべき乗も同様にこの条件を満たします [つまり、最初の $t$ のすべての倍数は同じ性質を持ちます]。

$フェルマーは、 aが$ $p$ の倍数である場合を考慮せず、また彼の主張を証明せず、単に次のように述べているだけである。^{[ 4 ]}

進行状況やプレミアの一般的な提案など。 de quoi je vous envoierois la démonstration、si je n'appréhendois d'être trop long。

(そしてこの命題は一般的にすべての数列[原文ママ]とすべての素数に当てはまります。長くなりすぎる恐れがなければ、その証明をお送りしたいところです。) ^{[ 5 ]}

オイラーは1736年にサンクトペテルブルク科学アカデミー紀要に掲載された「Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio」（英語では「素数に関するいくつかの定理の証明」）という論文で最初の証明を発表したが^{[ 6 ]}^{[ 7 ]}、ライプニッツは1683年以前の未発表原稿でほぼ同じ証明を発表していた^{[ 3 ]。}

「フェルマーの小定理」という用語は、おそらく1913年にクルト・ヘンゼルの『数論』で初めて印刷物で使用されたと思われる。^[⁸^]

Für jede endliche Gruppe besteht nun ein Fundamentalsatz、welcher der kleine Fermatsche Satz genannt zu werden pflegt、weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist。

（すべての有限群には、フェルマーが最初にその非常に特殊な部分を証明したことから、一般的にフェルマーの小定理と呼ばれる基本的な定理が存在する。）

英語での初期の使用例は、 AA AlbertのModern Higher Algebra (1937) の 206 ページで「いわゆる「小さな」フェルマーの定理」に言及している箇所に見られる。 ^{[ 9 ]}

さらなる歴史

$一部の数学者は、 p$ が素数である場合に限り $2 p \equiv 2 (mod p)$ が成り立つという関連仮説 (時として誤って中国仮説と呼ばれる) を独自に提唱した。実際、「もし」の部分は正しく、フェルマーの小定理の特殊な場合である。しかし、「もし」の部分は誤りである。例えば、 $2$ $341$ $\equiv 2 (mod 341)$ であるが、341 = 11 × 31 は2 を基数とする擬素数である。以下を参照。

証明

フェルマーの小定理にはいくつかの証明が知られている。それはしばしばオイラーの定理の系として証明される。

一般化

オイラーの定理はフェルマーの小定理の一般化である。任意の法 $n$ と $n$ と互いに素な任意の整数 $a$ に対して、次の式が成り立つ。

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

ここで、 $φ (n)は$ オイラーのトーシェント関数（nと互いに素な1から $nまでの整数の数を数える関数$ $）$ を表します。フェルマーの小定理は確かに特殊なケースです。なぜなら、 $n$ が素数の場合、 $φ (n) = n - 1と$ なるからです。

オイラーの定理の系は次の通りである。任意の正の整数 $n$ に対して、整数 $a が$ $n$ と互いに素である場合、 $x\equiv y{\pmod {\varphi (n)}}\quad {\text{は}}\quad a^{x}\equiv a^{y}{\pmod {n}}を意味する$ 任意の整数 $x$ と $y$ に対して。これはオイラーの定理から導かれる。なぜなら、 $x\equiv y{\pmod {\varphi (n)}}$ すると、ある整数 $kに対して$ $x = y + kφ (n)$ となり、 $a^{x}=a^{y+\varphi (n)k}=a^{y}(a^{\varphi (n)})^{k}\equiv a^{y}1^{k}\equiv a^{y}{\pmod {n}}.$

$n$ が素数の場合、これはフェルマーの小定理の系でもあります。これはモジュラー演算で広く用いられており、大きな指数を持つモジュラーべき乗を $n$ より小さい指数に還元することを可能にします。

オイラーの定理は、公開鍵暗号、特にRSA暗号システムにおいて、nが素数でない場合に、通常次の $よう$ に使用されます。^[¹⁰^] $y=x^{e}{\pmod {n}},$ $y$ 、 $e$ 、 $n$ の値から $x$ を取得するのは、 $φ$ $($ $n$ $)$ が分かっていれば簡単です。^[¹¹^]実際、拡張ユークリッドアルゴリズムでは、 $e の$ 法 $φ$ $($ $n$ $)$ のモジュラー逆数、つまり、次の条件を満たす整数 $f$ を計算することができます。 $ef\equiv 1{\pmod {\varphi (n)}}.$ したがって、 $x\equiv x^{ef}\equiv (x^{e})^{f}\equiv y^{f}{\pmod {n}}.$

一方、 $n = pq が$ 2 つの異なる素数の積である場合、 $φ (n) = (p - 1)(q - 1)$ となります。この場合、 $n$ と $e$ から $f を求めることは、$ $φ$ $($ $n$ $)$ を計算するのと同じくらい困難です(これは証明されていませんが、 $φ$ $($ $n$ $)$ を知らずに $f$ を計算するアルゴリズムは知られていません)。n だけがわかっている $場合$ 、 $φ$ $($ $n$ $)$ $= ($ $p$ $-$ $1)($ $q$ $- 1)$ であり、逆に、因子 pと $qは方程式$ $x$ $2$ $- ($ $n$ $-$ $φ$ $($ $n$ $) + 1)$ $x$ $+$ $n$ $= 0$ $の$ $($ 整数) 解であるため、 $φ ($ $n$ ) の計算は本質的に n の因数分解と同じ困難さになります。

RSA暗号システムの基本的な考え方は次のとおりです。メッセージ $xが$ $n$ と $e$ の公開値を使用して $y = x e (mod n)$ として暗号化されている場合、現在の知識では、 $n$ の（秘密の）因子 $p$ と $qを$ 見つけない限り、復号化することはできません。

フェルマーの小定理は、カルマイケル関数やカルマイケルの定理、そして群論におけるラグランジュの定理とも関連している。

コンバース

フェルマーの小定理の逆はカーマイケル数には当てはまらない。しかし、その逆のやや弱い変形としてレーマーの定理がある。

整数 $a$ が存在して、 $a^{p-1}\equiv 1{\pmod {p}}$ $また、 p$ $-$ $1$ を割り切るすべての素数 $qに対して、$ $a^{(p-1)/q}\not \equiv 1{\pmod {p}},$ すると $p$ は素数である。

この定理は、重要な素数判定法であるルーカス素数判定法とプラット素数証明書の基礎を形成している。

擬素数

$a$ と $p$ が互いに素な数で、 $a p -1 - 1が$ $p$ で割り切れる場合、 $p は$ 素数である必要はありません。そうでない場合、 $pは$ $a$ を基数とする(フェルマー) 擬素数と呼ばれます。2 を基数とする最初の擬素数は、1820 年にピエール・フレデリック・サリュスによって発見されました。341 = 11 × 31 です。^[¹²^]^[¹³^]

基底 $a$ に対してフェルマー擬素数である数 $pを、$ $p$ と互いに素な $すべて$ の数 a に対して、カーマイケル数と呼ぶ。あるいは、等式を満たす任意の数 $pは、$ $\gcd \left(p,\sum _{a=1}^{p-1}a^{p-1}\right)=1$ は素数かカーマイケル数のいずれかである。

ミラー・ラビン素数判定法

ミラー・ラビン素数判定法は、フェルマーの小定理の次の拡張を使用する。^{[ 14 ]}

$pが$ 奇素数で、 $p - 1 = 2 s d$ $(s > 0$ かつ $d$ が奇数 > 0)である場合、 $p$ と互いに素なすべての $a$ に対して、 $a$ $d$ $\equiv 1 (mod$ $p$ $)または$ $0 \leq$ $r$ $<$ $s$ かつ $a$ $2$ $r$ $d$ $\equiv -1 (mod$ $p$ $)$ となるような $r が$ 存在する。

この結果は、 $p が$ 奇素数である場合、 $pを法とする整数は$ 有限体を形成し、その中で 1 は $pを法とする 1 と -1$ $の$ 2 つの平方根を持つという事実から、フェルマーの小定理から導き出すことができる。

$a$ $\equiv 1 (mod$ $p$ $)の場合、$ $a d$ $\equiv 1 (mod$ $p$ $)$ が自明に成り立つことに注意してください。これは、合同関係が指数法則と互換性があるためです。また、 $d$ が奇数であるため、 $a$ $\equiv -1 (mod$ $p$ $)の場合、$ $a$ $d$ $=$ $a$ $2$ $0$ $d$ $\equiv -1 (mod$ $p$ $)$ が自明に成り立ちます。これが、通常、 $1 <$ $a$ $<$ $p$ $- 1$ の範囲でランダムな $a を$ 選択する理由です。

ミラー・ラビン判定法はこの性質を次のように利用します。素数判定が必要な奇数 $pが与えられたとき、$ $p - 1 = 2 s d$ ( $s > 0$ 、 $d は奇数 > 0) と書き、$ $1 <$ $a$ $<$ $p$ $- 1$ となるようなランダムな $a$ を選びます。次に、 $b$ $=$ $a$ $d$ $mod$ $p$ を計算します。b が 1 でも −1 でもない場合 $は$ 、 −1 になるか $s$ $- 1$ 回二乗するまで、 $p$ を法として繰り返し二乗します。b ≠ 1 で、二乗しても −1 が得られない場合 $、$ $p$ は $合成$ 数であり、 $a は$ $p$ が合成数であることの証拠となります。そうでない場合、 $pは$ a を基数とする強い確率の素数です。つまり、素数である場合もそうでない場合もあります。p が合成数の場合 $、判定法がそれを強い確率の素数と宣言する確率$ は最大で 1/4 であり、その場合、p $は$ 強い擬似素数であり、 $aは$ 強い嘘つきです。したがって、 $k 回$ の決定的なランダムテストの後、 $p$ が複合値である確率は最大で 4 ⁻^kであり、 $k を$ 増やすことで望むだけ低くすることができます。

要約すると、このテストは、ある数が合成数であることを証明するか、素数であると主張するもので、誤りの確率は任意に低く設定できます。このテストは実装が非常に簡単で、既知のすべての決定論的テストよりも計算効率に優れています。そのため、一般的に素数性の証明を開始する前に使用されます。

注記

↑ Long 1972 、pp. 87–88。
↑ Pettofrezzo & Byrkit 1970 、pp. 110–111。
1 2 3バートン 2011 、p. 514。
↑フェルマー、ピエール (1894)、タンナリー、P.;ヘンリー、C. (編)、Oeuvres de Fermat。第 2 巻: 通信、パリ: ゴティエヴィラール、206 ～ 212ページ（フランス語）
↑英語訳については、 Mahoney 1994 、p. 295を参照。
↑オイラー、レオンハルト (1736)。「Theorematum quorundam ad numeros primos spectantium Demonstratio」[素数に関する特定の定理の証明]。Commentarii Academiae Scientiarum Imperialis Petropolitanae (サンクトペテルブルク帝国科学アカデミー回想録) (ラテン語)。8 : 141–146 .
↑ Ore 1988 、p. 273
↑ヘンゼル、クルト (1913)。Zahlentheorie [整数論] (ドイツ語)。ベルリンとライプツィヒ、ドイツ: GJ Göschen。 p. 103.
↑アルバート2015 、p.206
↑トラップ、ウェイド；ワシントン、ローレンス C. (2002)、『暗号理論入門』、プレンティス・ホール、78 ページ、ISBN 978-0-13-061814-6
↑ $y が$ $n$ と互いに素でない場合、オイラーの定理は機能しませんが、このケースは非常にまれであるため考慮する必要はありません。実際、もし偶然に発生した場合、 $n$ の素因数分解が容易になり、検討対象の RSA のインスタンスが破られてしまいます。
↑ Sloane, N. J. A. (編). "数列A128311 (2 ⁿ⁻¹ −1をnで割った余り)" .オンライン整数列百科事典. OEIS Foundation.
↑フレデリック・サラス(1819–1820)。"Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil" [定理の誤りの証明はこのコレクションの第 9 巻の 320 ページに記載されています]。Annales de Mathématiques Pures et Appliquées (フランス語)。10：184–187。
↑レンペ＝ギレン、ラッセ；ワルデッカー、レベッカ（2013年12月11日）。「4.5.1. 補題（素数を法とする1の根）」。『素数判定入門』。アメリカ数学会。ISBN 9780821898833。

参考文献

アルバート、A.エイドリアン（2015）[1938]、『現代高等代数学』、ケンブリッジ大学出版局、ISBN 978-1-107-54462-8
バートン、デイビッド・M. (2011)、『数学の歴史／入門』（第7 版）、マグロウヒル、ISBN 978-0-07-338315-6
Long, Calvin T. (1972), 『数論入門』（第2 版）, レキシントン：DC Heath and Company , LCCN 77171950
マホニー、マイケル・ショーン（1994）、『ピエール・ド・フェルマーの数学的経歴、1601-1665』（第2 版）、プリンストン大学出版局、Bibcode：1994mcpd.book.....M、ISBN 978-0-691-03666-3
オレ、オイスタイン（1988）[1948]、『数論とその歴史』、ドーバー出版、ISBN 978-0-486-65620-5
Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), 『数論の基礎』、Englewood Cliffs: Prentice Hall、LCCN 71081766

さらに読む

パウロ・リベンボイム（1995）。素数記録の新版（第3版）。ニューヨーク：シュプリンガー・フェルラーク。ISBN 0-387-94457-5 22～25ページ、49ページ。

外部リンク

ウィキメディア・コモンズにあるフェルマーの小定理に関連するメディア
ヤーノシュ・ボリャイと擬似素数（ハンガリー語）
フェルマーの小定理（cut-the-knot）
カット・ザ・ノットのオイラー関数と定理
フェルマーの小定理とソフィーの証明
「フェルマーの小定理」、数学百科事典、EMS Press、2001年 [1994年]
ワイススタイン、エリック・W. 「フェルマーの小定理」 . MathWorld .
ワイススタイン、エリック・W. 「フェルマーの小定理の逆」 . MathWorld .

[1] Long 1972 、pp. 87–88。

[2] Pettofrezzo & Byrkit 1970 、pp. 110–111。

[Burton-3] 1 2 3バートン 2011 、p. 514。

[4] フェルマー、ピエール (1894)、タンナリー、P.;ヘンリー、C. (編)、Oeuvres de Fermat。第 2 巻: 通信、パリ: ゴティエヴィラール、206 ～ 212ページ（フランス語）

[5] 英語訳については、 Mahoney 1994 、p. 295を参照。

[6] オイラー、レオンハルト (1736)。「Theorematum quorundam ad numeros primos spectantium Demonstratio」[素数に関する特定の定理の証明]。Commentarii Academiae Scientiarum Imperialis Petropolitanae (サンクトペテルブルク帝国科学アカデミー回想録) (ラテン語)。8 : 141–146 .

[7] Ore 1988 、p. 273

[8] ヘンゼル、クルト (1913)。Zahlentheorie [整数論] (ドイツ語)。ベルリンとライプツィヒ、ドイツ: GJ Göschen。 p. 103.

[9] アルバート2015 、p.206

[10] トラップ、ウェイド；ワシントン、ローレンス C. (2002)、『暗号理論入門』、プレンティス・ホール、78 ページ、ISBN 978-0-13-061814-6

[11] $y が$ $n$ と互いに素でない場合、オイラーの定理は機能しませんが、このケースは非常にまれであるため考慮する必要はありません。実際、もし偶然に発生した場合、 $n$ の素因数分解が容易になり、検討対象の RSA のインスタンスが破られてしまいます。

[12] Sloane, N. J. A. (編). "数列A128311 (2 ⁿ⁻¹ −1をnで割った余り)" .オンライン整数列百科事典. OEIS Foundation.

[13] フレデリック・サラス(1819–1820)。"Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil" [定理の誤りの証明はこのコレクションの第 9 巻の 320 ページに記載されています]。Annales de Mathématiques Pures et Appliquées (フランス語)。10：184–187。

[14] レンペ＝ギレン、ラッセ；ワルデッカー、レベッカ（2013年12月11日）。「4.5.1. 補題（素数を法とする1の根）」。『素数判定入門』。アメリカ数学会。ISBN 9780821898833。

[

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[

[ 9 ]

[

[

[

[

[ 14 ]