フェルマーの小定理
出典: Wikipedio
|
|
数論において、フェルマーの小定理（フェルマーのしょうていり、Fermat's little theorem）は素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。
目次 |
概要
p を素数とし、a を p の倍数でない整数（a と p は互いに素）とするときに、
- <math>a^{p-1} \equiv 1 \pmod{p}</math>
すなわち a を p - 1 乗したものを p で割ったあまりは 1 になるというもの。有名なフェルマーの最終定理と区別するためにあえて「小」定理と称されている。
この定理はピエール・ド・フェルマーの名を冠するが、フェルマーの他の予想と同じく、フェルマー自身によって証明が与えられていたことが確認されているわけではない。この定理に対する証明はゴットフリート・ライプニッツによって初めて与えられた。
証明
二項定理から、数学的帰納法を用いて証明する方法が簡便である。ここでは、
- <math>a^{p} \equiv a \pmod{p}</math>
つまり a を p 乗したものを p で割ったあまりは a を p で割ったあまりに等しいという形の命題として証明する。
- (m + 1)p という式を展開することを考える。これは公式により、
mp + pC1mp-1 + pC2mp-2 + … + pCp-1m + 1
となる。 - ここで両端の項以外はすべての項に pCk が因数として含まれている。これは、p が素数であれば k が 1 以上 p 未満である限り必ず p で割り切れる。なぜなら pCk = p!/(p-k)!k! であり、p が素数であるなら分子には p が含まれているものの分母に p やその倍数は含まれないからである。
- すると、両端の項以外は p で割り切れる。(m + 1)p を p で割ったあまりは、残る mp + 1 を p で割ったあまりと等しいことになる。
- ここで、m = 1 とする。2p = (1 + 1)p を p で割ったあまりは 1p + 1 = 2 ということになり、命題は a = 2 の場合に正しいことが証明された。
- a に関する帰納法で示すために、a = k で命題が成立していると仮定する。ステップ3により、(k + 1)p を p で割ったあまりは、kp + 1 を p で割ったあまりに等しい。さらにこれは、帰納法の仮定により、k + 1 を p で割ったあまりに等しい。したがって命題は a = k + 1 でも成立する。数学的帰納法によって 2 以上のすべての a について命題は成立することになる。
- a = 0, 1 の場合は命題の成立することが自明。
（証明終わり）
オイラーの定理
後になってレオンハルト・オイラーはこの定理を拡張し、a を n と互いに素な整数とするときに、
- <math>a^{\varphi(n)} \equiv 1 \pmod{n}</math>
が成り立つことを示した。ここで、<math>\varphi(n)</math> は n 未満の n に素な自然数の個数を表し、オイラー関数 と呼ばれる。
n が素数のときに限れば、<math>\varphi(n)=n-1</math> であるからこれはフェルマーの小定理に一致する。
カーマイケルの定理
<math>m=\varphi(n)</math> とすれば、<math>a^{m} \equiv 1 \pmod{n}</math> がnと互いに素な全てのaに対して成り立つが、<math>\varphi(n)</math> はこの性質を満たす最小の m とは限らない。カーマイケルの定理はオイラーの定理を精緻化したもので、最小の m を与える。
Template:仮リンク λ(n) を以下のように再帰的に定義する。
n = 2e なら、
- <math>\lambda(2^e)=\begin{cases}1&\,:e=1\\2&\,:e=2\\2^{e-2}&\,:e\ge 3\end{cases}</math>
n が奇素数 p を用いて n = pe と書けるなら、
- <math>\lambda(p^e)=p^{e-1}(p-1)\,</math>
n が <math>p_1{}^{e_1}\cdots p_k{}^{e_k}</math> と素因数分解できるなら、
- <math>\lambda(p_1{}^{e_1}\cdots p_k{}^{e_k})=\mathrm{lcm}(\lambda(p_1{}^{e_1}),\ldots,\lambda(p_k{}^{e_k}))</math>
ここで lcm は最大公約数。
カーマイケルの定理は、a と n が互いに素なとき、
- <math>a^{\lambda(n)} \equiv 1 \pmod{n}</math>
が成立する、という定理である。
<math>\lambda(n)</math> が n - 1 の約数であるとき、n はカーマイケル数と呼ばれ、自身と互いに素であるような全ての底でフェルマーテストを通過する絶対擬素数となる。
フェルマーテスト
フェルマーテストは、 フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムである。
フェルマーの小定理の対偶をとると、これは次のように、自然数 n が合成数であるための十分条件を与える。
- 対偶
- n と互いに素な 整数 a が
- <math>a^{n-1} \ \not\equiv\ 1 \pmod{n}</math>
- を満たせば、このとき n は合成数である。
この十分条件を用いて、次のように自然数 n の素数判定を行う。
- パラメータとして、2 以上 n 未満の自然数 a を1つ定める。
- a と n が互いに素でなければ「n は合成数」と出力して終了。
- <math>a^{n-1} \ \not\equiv\ 1 \pmod{n}</math> ならば「n は合成数」と出力して終了する。そうでないとき「n は確率的素数」と出力して終了する。
フェルマーテストが「合成数」と出力したとき、上のフェルマーの小定理の対偶によって n は実際に合成数である。しかし、上の対偶は十分条件を与えるのみで必要条件を与えるものではないので、「確率的素数」と出力された場合でも n は実際に素数であるとは限らない。素数ではないにもかかわらず「確率的素数」と判定されてしまう合成数は擬素数と呼ばれる。
疑わしければ、「確率的素数」と出力された場合にはまた異なる a を用いて再びテストを行う。十分な回数だけ a を取り替えて繰り返せば、フェルマーテストが「確率的素数」と判定した数は実際に素数である可能性が高い。
しかし、カーマイケル数または絶対擬素数と呼ばれる "反例" もある。カーマイケル数は合成数であるにも関わらず、ほとんどいかなる a を用いても「確率的素数」と判定されてしまう。従って、フェルマーテストは完全な素数判定法ではない。
フェルマーテストを改善するアルゴリズムとしては、ラビン-ミラー素数判定法やAKS素数判定法がある。
一般化
フェルマーの小定理・オイラーの定理は一般の有限群の定理に拡張できる。G を位数 m の有限群とすると、G の任意の元 g に対して gm は単位元に一致する。オイラーの定理は G が乗法群 (Z/nZ)× のときの場合であり、フェルマーの小定理はさらに n が素数の場合である。
参考文献
- 高木貞治『初等整数論講義〈第2版〉』共立出版、1971年、67頁、53-54頁。ISBN 4-320-01001-9
- G.H.ハーディ、E.M.ライト『数論入門Ⅰ』シュプリンガー・フェアラーク東京、2001年、82-107頁。ISBN 4-431-70848-0
外部リンク
bg:Малка теорема на Ферма ca:Petit teorema de Fermat cs:Malá Fermatova věta de:Kleiner fermatscher Satz en:Fermat's little theorem eo:Malgranda teoremo de Fermat es:Pequeño teorema de Fermat fa:قضیه کوچک فرما fi:Fermat'n pieni lause fr:Petit théorème de Fermat he:המשפט הקטן של פרמה hu:Kis Fermat-tétel id:Teorema kecil Fermat it:Piccolo teorema di Fermat ka:ფერმას მცირე თეორემა kk:Ферманың кіші теоремасы ko:페르마의 소정리 lt:Mažoji Ferma teorema mn:Фермагийн бага теорем nl:Kleine stelling van Fermat pl:Małe twierdzenie Fermata pt:Teste de primalidade de Fermat ro:Mica teoremă a lui Fermat ru:Малая теорема Ферма sk:Malá Fermatova veta sl:Fermatov mali izrek sr:Мала Фермаова теорема sv:Fermats lilla sats ta:ஃபெர்மாவின் சிறிய தேற்றம் th:ทฤษฎีบทเล็กของแฟร์มาต์ tr:Fermat'nın küçük teoremi uk:Мала теорема Ферма vi:Định lý nhỏ Fermat zh:费马小定理
