フェルマーの小定理

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

たとえば、a = 2、p = 7の場合、2 ⁷ = 128となり、128 − 2 = 126 = 7 × 18は7の整数倍になります。

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

たとえば、a = 2、p = 7の場合、2 ⁶ = 64となり、64 − 1 = 63 = 7 × 9は7の倍数になります。

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

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

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

フェルマーの元々の発言は

最も重要な手段が失敗しないことを宣伝し、進行状況を確認し、最も重要な方法を複数の方法で説明します。 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.${\displaystyle -1}$${\displaystyle -1}$

これを翻訳すると、理解しやすいように括弧内に説明と数式が追加され、次のようになります。

すべての素数 [ p ] は、任意の [幾何] 数列 [ a 、 a 2 、 a 3 、… ] のべき乗マイナス 1 のいずれかを必ず割り切れます[つまり、 pが^a t – ¹を割り切る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年にサンクトペテルブルクアカデミーの紀要に「素数に関する特定の定理の証明」と題する論文を掲載し、最初の証明を行った^{[6] [7]}が、ライプニッツは1683年より前の未発表の原稿でほぼ同じ証明を行っていた^[3]。

「フェルマーの小定理」という用語は、1913年にクルト・ヘンゼルの著書『定理』で初めて印刷物に使用されたと考えられる。^[8]

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アルバートの「現代高等代数」（1937年）で、206ページの「いわゆる「小さな」フェルマーの定理」に言及している。^[9]

何人かの数学者は、 pが素数である場合にのみ2 ^p ≡ 2 (mod p )であるという関連する仮説 (誤って中国仮説と呼ばれることもある) を独自に立てました。確かに、「もし」の部分は正しく、フェルマーの小定理の特殊なケースです。しかし、「もし」の部分は誤りです。たとえば、2 ³⁴¹ ≡ 2 (mod 341)ですが、 341 = 11 × 31 は 2 を底とする擬素数です。以下を参照してください。

フェルマーの小定理の証明はいくつか知られています。これはオイラーの定理の系としてよく証明されます。

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

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

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

オイラーの定理の系は、任意の正の整数nに対して、整数aがnと互いに素であれば、 任意の整数xとyに対してである。これはオイラーの定理から導かれる。なぜなら、であれば、ある整数kに対してx = y + kφ ( n )となり、 $${\displaystyle x\equiv y{\pmod {\varphi (n)}}\quad {\text{implies}}\quad a^{x}\equiv a^{y}{\pmod {n}},}$$${\displaystyle x\equiv y{\pmod {\varphi (n)}}}$$${\displaystyle 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が素数でない場合、典型的には次のように用いられる。^[10] y、e、nの値からxを 取得することは 、 φ ( n )がわかれば容易である。^[11]実際、拡張ユークリッド互除法では、eを法としてφ ( n )のモジュラー逆数、つまり 整数fを計算することができる 。従って、 $${\displaystyle y=x^{e}{\pmod {n}},}$$$${\displaystyle ef\equiv 1{\pmod {\varphi (n)}}.}$$$${\displaystyle 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 )の計算は、φ ( n ) = ( p − 1)( q − 1)であり、逆に、因数pとqは、方程式x ² – ( n − φ ( n ) + 1) x + n = 0の (整数) 解であるため、 n の因数分解と本質的に同じ難しさがあります。

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

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

フェルマーの小定理の逆はカーマイケル数では成り立ちません。しかし、逆の少し弱い変形としてレーマーの定理があります。

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

この定理は、重要な素数判定であるルーカス素数判定と、プラットの素数判定証明書の基礎となります。

もしaとp が互いに素な数で、a ^{p −1} − 1がpで割り切れる場合、p は素数である必要はない。もし素数でない場合、p はa を底とする（フェルマーの）擬素数と呼ばれる。 2 を底とする最初の擬素数は、1820年にピエール・フレデリック・サリュスによって発見された：341 = 11 × 31。^{[12] [13]}

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

ミラー・ラビン素数判定では、フェルマーの小定理の次の拡張が用いられる: ^[14]

p が奇数の素数で、s > 0かつd が奇数 > 0であるとき、 p − 1 = 2 ^s dであるとき、 pと互いに素なすべてのaに対して、a ^d ≡ 1 (mod p )であるか、 0 ≤ r < sかつa ^{2 r d} ≡ −1 (mod p )となるr が存在します。

この結果は、p が奇数の素数である場合、 pを法とする整数が有限体を形成し、その中で p を法とする 1 には p を法とする 1 と -1 のちょうど 2 つの平方根が存在するという事実によって、フェルマーの小定理から推測できます。

合同関係はべき乗と互換性があるので、 a ^d ≡ 1 (mod p )はa ≡ 1 (mod p )に対して自明に成り立つことに注意してください。また、同じ理由で、 d は奇数なので、 a ^d = a ^{2 0 d} ≡ −1 (mod p )はa ≡ −1 (mod p )に対して自明に成り立ちます。これが、通常、区間1 < a < p − 1でランダムなa を選択する理由です。

ミラー・ラビン検定では、この特性を次のように使用します。素数かどうかを判定する必要がある奇数の整数p が与えられた場合、 s > 0かつd odd > 0としてp − 1 = 2 ^s dと書き、 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 を増やすことで望みどおりに低くすることができます。

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

• アルバート、A.エイドリアン（2015）[1938]、現代高等代数、ケンブリッジ大学出版局、ISBN 978-1-107-54462-8
• バートン、デイビッド・M.（2011）、数学の歴史/入門（第7版）、マグロウヒル、ISBN 978-0-07-338315-6
• ロング、カルビン T. (1972)、初等数論入門(第 2 版)、レキシントン: DC ヒース アンド カンパニー、LCCN  77171950
• マホニー、マイケル・ショーン（1994年）『ピエール・ド・フェルマーの数学史 1601-1665』（第2版）、プリンストン大学出版局、ISBN 978-0-691-03666-3
• オーレ、オイステイン（1988）[1948]、数論とその歴史、ドーバー、ISBN 978-0-486-65620-5
• ペットフレッツォ、アンソニー J.; バーキット、ドナルド R. (1970)、Elements of Number Theory、Englewood Cliffs: Prentice Hall、LCCN  71081766

• パウロ・リーベンボイム(1995)。『素数記録の新書』 （第3版） 。ニューヨーク：シュプリンガー出版社。ISBN 0-387-94457-5。pp . 22–25, 49。 

• ウィキメディア・コモンズのフェルマーの小定理に関連するメディア
• ヤーノシュ・ボリャイと擬似素数（ハンガリー語）
• フェルマーの小定理をカット・ザ・ノットで
• 結び目を切る際のオイラー関数と定理
• フェルマーの小定理とソフィーの証明
• 「フェルマーの小定理」、数学百科事典、EMS Press、2001 [1994]
• Weisstein, Eric W.「フェルマーの小定理」。MathWorld。
• Weisstein, Eric W.「フェルマーの小定理の逆」。MathWorld。