フェルマーの小定理のソースを表示

{{混同|フェルマーの大定理|フェルマーの最終定理|x1=自然数の冪乗の和に関する定理の}}
[[数論]]において、'''フェルマーの小定理'''（フェルマーのしょうていり、{{lang-en-short|Fermat's little theorem}}）は、[[素数]]の性質についての[[定理]]であり、実用としても[[RSA暗号]]に応用されている定理である。

== 概要 ==
<math>p</math> を素数とし、 <math>a</math> を整数とすると、

:<math>a^{p} \equiv a \pmod p</math>

が成立すると言う定理である。また、 <math>p</math> を素数とし、 <math>a</math> を <math>p</math> の倍数でない整数（ <math>a</math> と <math>p</math> は[[互いに素 (整数論)|互いに素]]）とするときに、

:<math>a^{p-1} \equiv 1 \pmod p</math>

が成立する。すなわち、 <math>a</math> の <math>p-1</math> 乗を <math>p</math> で割った余りは <math>1</math> である。有名な[[フェルマーの最終定理]]と区別するためにあえて「小」定理と称されている。

この定理は[[ピエール・ド・フェルマー]]の名を冠するが、フェルマーの他の予想と同じく、フェルマー自身によって[[証明 (数学)|証明]]が与えられていたことが確認されているわけではない。この定理に対する証明は[[ゴットフリート・ライプニッツ]]によって初めて与えられた。

== 証明 ==
3通りの証明を示す。

=== 証明(1) ===
[[二項定理]]から、[[数学的帰納法]]を用いて証明する方法が簡便である。

補題：「 <math>\left( m+1\right)^{p}</math> を <math>p</math> で割った余りは <math>m^{p}+1</math> を <math>p</math> で割った余りに等しい。」

（補題の証明）

:<math>(m + 1)^p = m^p + {}_p\mathrm{C}_1 m^{p-1} + {}_p\mathrm{C}_2 m^{p-2} + \dotsb + {}_p\mathrm{C}_{p-1} m + 1</math>（[[二項定理]]）

右辺の両端以外の二項係数 <math>{}_p\mathrm{C}_k</math> はすべて <math>p</math> の倍数である。なぜなら、
:<math>{}_p \mathrm{C}_k = \frac{p(p-1) \dotsb (p-k+1)}{k (k-1) \dotsb 1}</math>
であり、 <math>p</math> は素数であって <math>k<p</math> なので、分子に含まれる <math>p</math> が約分されることはないからである。

したがって、 <math>\left( m+1\right)^{p}</math> を <math>p</math> で割った余りは、両端の項 <math>m^{p}+1</math> を <math>p</math> で割った余りに等しい。（補題の証明終）

命題「 <math>a^{p}\equiv a\pmod{p}</math> 」を、 <math>a</math> についての数学的帰納法で証明する。

補題に <math>m=1</math> を代入すると、 <math>2^{p}=\left( 1+1\right)^{p}</math> を <math>p</math> で割った余りは <math>1^{p}+1=2</math> となり、 <math>a=2</math> のとき成り立つ。

命題が、 <math>a=k</math> のとき成り立つと仮定する。

補題から、 <math>\left( k+1\right)^{p}</math> を <math>p</math> で割った余りは <math>k^{p}+1</math> を <math>p</math> で割った余りに等しい。帰納法の仮定によって <math>k^{p}</math> を <math>p</math> で割った余りは <math>k</math> を <math>p</math> で割った余りに等しいから、 <math>\left( k+1\right)^{p}</math> を <math>p</math> で割った余りは <math>k+1</math> を <math>p</math> で割った余りに等しい。

したがって、命題は <math>a=k+1</math> のときも成り立つ。

数学的帰納法によって、命題は <math>a\geqq 2</math> に対して成り立つ。また、 <math>a=0,\ 1</math> のときは、代入してみると明らかに成り立つので、命題は <math>a\geqq 0</math> に対して成り立つ。

（証明終）

=== 証明(2) ===
上の補題と同様に、<math>(x+y)^p \equiv x^p + y^p \pmod p</math> が示せる。これより、

:<math>\begin{align}
a^p &= [1+(a-1)]^p \\
&\equiv 1^p + [1+(a-2)]^p \\
&\equiv 1 + 1^p + [1+(a-3)]^p \\
&\equiv a \pmod p
\end{align}</math>

（証明終）

=== 証明(3) ===
<math>p</math> を素数とし、 <math>a</math> と <math>p</math> が互いに素とするときに、

:<math>a^{p-1} \equiv 1 \pmod p</math>

が成立することを、ここで証明する。

集合 <math>\left\{ 1,\ 2,\ 3,\ldots ,\ p-1\right\}</math> は、全体として法 <math>p</math> の下で <math>\left\{ a,\ 2a,\ 3a,\ldots ,\ \left( p-1\right)a\right\}</math> と合同である。（[[背理法]]による証明）もし後者の集合内に

:<math>ia \equiv ja \pmod p</math>

となる <math>i,\ j</math> (ただし、 <math>i\neq j</math> )が存在したとする。すると、 <math>a</math> と <math>p</math> が[[互いに素 (整数論)|互いに素]]なので、 <math>i\equiv j\pmod{p}</math> となり、 <math>0<i,\ j<p</math> であることから、 <math>i=j</math> となり、矛盾する。したがって、二つの集合は全体として合同であることが分かった。

それぞれの集合の要素をすべて掛け合わせると、

:<math>(p-1)! \equiv (p-1)! \  a^{p-1} \pmod p</math>
となる。 <math>p</math> が素数であることから、 <math>p</math> と <math>\left( p-1\right)!</math> とは互いに素なので、

:<math>a^{p-1}\equiv 1\pmod{p}</math>

（証明終）

==性質==
フェルマーの小定理は、乱数を発生する用途に使われることがある。しかし、このような場合、あらゆる（p と互いに素な）a について、
:<math> b = a^n \pmod p </math>
が、<math>n= 1 .. p-1 </math> に沿って
:<math> 1 \leq b < p </math> 
の全要素を順繰りに巡ることを保証しているわけではない点には注意すべきである。実際、次の各表では、<math>n=p-1</math> である右端の列が全てゼロになることは確かだが、それ以外にもゼロは出現している。

<math>p=3</math> の場合：
{|class="wikitable" style=text-align:center
!rowspan="2" colspan="2"|
!colspan="2"|<math>n</math>
|-
!<math>1</math>
!<math>2</math>
|-
!rowspan="2"|<math>a</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
|-
!|<math>2</math>
|<math>2</math>
!|<math>1</math>
|}

<math>p=5</math> の場合：
{|class="wikitable" style=text-align:center
!rowspan="2" colspan="2"|
!colspan="4"|<math>n</math>
|-
!<math>1</math>
!<math>2</math>
!<math>3</math>
!<math>4</math>
|-
!rowspan="4"|<math>a</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
|-
!|<math>2</math>
|<math>2</math>
|<math>4</math>
|<math>3</math>
!|<math>1</math>
|-
!|<math>3</math>
|<math>3</math>
|<math>4</math>
|<math>2</math>
!|<math>1</math>
|-
!|<math>4</math>
|<math>4</math>
!|<math>1</math>
|<math>4</math>
!|<math>1</math>
|}

<math>p=7</math> の場合：
{|class="wikitable" style=text-align:center
!rowspan="2" colspan="2"|
!colspan="6"|<math>n</math>
|-
!<math>1</math>
!<math>2</math>
!<math>3</math>
!<math>4</math>
!<math>5</math>
!<math>6</math>
|-
!rowspan="6"|<math>a</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
|-
!|<math>2</math>
|<math>2</math>
|<math>4</math>
!|<math>1</math>
|<math>2</math>
|<math>4</math>
!|<math>1</math>
|-
!|<math>3</math>
|<math>3</math>
|<math>2</math>
|<math>6</math>
|<math>4</math>
|<math>5</math>
!|<math>1</math>
|-
!|<math>4</math>
|<math>4</math>
|<math>2</math>
!|<math>1</math>
|<math>4</math>
|<math>2</math>
!|<math>1</math>
|-
!|<math>5</math>
|<math>5</math>
|<math>4</math>
|<math>6</math>
|<math>2</math>
|<math>3</math>
!|<math>1</math>
|-
!|<math>6</math>
|<math>6</math>
!|<math>1</math>
|<math>6</math>
!|<math>1</math>
|<math>6</math>
!|<math>1</math>
|}

<math>p=11</math> の場合：
{|class="wikitable" style=text-align:center
!rowspan="2" colspan="2"|
!colspan="10"|<math>n</math>
|-
!<math>1</math>
!<math>2</math>
!<math>3</math>
!<math>4</math>
!<math>5</math>
!<math>6</math>
!<math>7</math>
!<math>8</math>
!<math>9</math>
!<math>10</math>
|-
!rowspan="10"|<math>a</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
|-
!<math>2</math>
|<math>2</math>
|<math>4</math>
|<math>8</math>
|<math>5</math>
|<math>10</math>
|<math>9</math>
|<math>7</math>
|<math>3</math>
|<math>6</math>
!|<math>1</math>
|-
!<math>3</math>
|<math>3</math>
|<math>9</math>
|<math>5</math>
|<math>4</math>
!<math>1</math>
|<math>3</math>
|<math>9</math>
|<math>5</math>
|<math>4</math>
!<math>1</math>
|-
!<math>4</math>
|<math>4</math>
|<math>5</math>
|<math>9</math>
|<math>3</math>
!<math>1</math>
|<math>4</math>
|<math>5</math>
|<math>9</math>
|<math>3</math>
!<math>1</math>
|-
!<math>5</math>
|<math>5</math>
|<math>3</math>
|<math>4</math>
|<math>9</math>
!<math>1</math>
|<math>5</math>
|<math>3</math>
|<math>4</math>
|<math>9</math>
!<math>1</math>
|-
!<math>6</math>
|<math>6</math>
|<math>3</math>
|<math>7</math>
|<math>9</math>
|<math>10</math>
|<math>5</math>
|<math>8</math>
|<math>4</math>
|<math>2</math>
!|<math>1</math>
|-
!<math>7</math>
|<math>7</math>
|<math>5</math>
|<math>2</math>
|<math>3</math>
|<math>10</math>
|<math>4</math>
|<math>6</math>
|<math>9</math>
|<math>8</math>
!|<math>1</math>
|-
!<math>8</math>
|<math>8</math>
|<math>9</math>
|<math>6</math>
|<math>4</math>
|<math>10</math>
|<math>3</math>
|<math>2</math>
|<math>5</math>
|<math>7</math>
!<math>1</math>
|-
!<math>9</math>
|<math>9</math>
|<math>4</math>
|<math>3</math>
|<math>5</math>
!<math>1</math>
|<math>9</math>
|<math>4</math>
|<math>3</math>
|<math>5</math>
!<math>1</math>
|-
!<math>10</math>
|<math>10</math>
!<math>1</math>
|<math>10</math>
!<math>1</math>
|<math>10</math>
!<math>1</math>
|<math>10</math>
!<math>1</math>
|<math>10</math>
!|<math>1</math>
|}

<math>p=13</math> の場合：
{|class="wikitable" style=text-align:center
!rowspan="2" colspan="2"|
!colspan="12"|<math>n</math>
|-
!<math>1</math>
!<math>2</math>
!<math>3</math>
!<math>4</math>
!<math>5</math>
!<math>6</math>
!<math>7</math>
!<math>8</math>
!<math>9</math>
!<math>10</math>
!<math>11</math>
!<math>12</math>
|-
!rowspan="12"|<math>a</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
!|<math>1</math>
|-
!<math>2</math>
|<math>2</math>
|<math>4</math>
|<math>8</math>
|<math>3</math>
|<math>6</math>
|<math>12</math>
|<math>11</math>
|<math>9</math>
|<math>5</math>
|<math>10</math>
|<math>7</math>
!|<math>1</math>
|-
!<math>3</math>
|<math>3</math>
|<math>9</math>
!<math>1</math>
|<math>3</math>
|<math>9</math>
!<math>1</math>
|<math>3</math>
|<math>9</math>
!<math>1</math>
|<math>3</math>
|<math>9</math>
!|<math>1</math>
|-
!<math>4</math>
|<math>4</math>
|<math>3</math>
|<math>12</math>
|<math>9</math>
|<math>10</math>
!<math>1</math>
|<math>4</math>
|<math>3</math>
|<math>12</math>
|<math>9</math>
|<math>10</math>
!|<math>1</math>
|-
!<math>5</math>
|<math>5</math>
|<math>12</math>
|<math>8</math>
!<math>1</math>
|<math>5</math>
|<math>12</math>
|<math>8</math>
!<math>1</math>
|<math>5</math>
|<math>12</math>
|<math>8</math>
!<math>1</math>
|-
!<math>6</math>
|<math>6</math>
|<math>10</math>
|<math>8</math>
|<math>9</math>
|<math>2</math>
|<math>12</math>
|<math>7</math>
|<math>3</math>
|<math>5</math>
|<math>4</math>
|<math>11</math>
!|<math>1</math>
|-
!<math>7</math>
|<math>7</math>
|<math>10</math>
|<math>5</math>
|<math>9</math>
|<math>11</math>
|<math>12</math>
|<math>6</math>
|<math>3</math>
|<math>8</math>
|<math>4</math>
|<math>2</math>
!|<math>1</math>
|-
!<math>8</math>
|<math>8</math>
|<math>12</math>
|<math>5</math>
!<math>1</math>
|<math>8</math>
|<math>12</math>
|<math>5</math>
!<math>1</math>
|<math>8</math>
|<math>12</math>
|<math>5</math>
!<math>1</math>
|-
!<math>9</math>
|<math>9</math>
|<math>3</math>
!<math>1</math>
|<math>9</math>
|<math>3</math>
!<math>1</math>
|<math>9</math>
|<math>3</math>
!<math>1</math>
|<math>9</math>
|<math>3</math>
!<math>1</math>
|-
!<math>10</math>
|<math>10</math>
|<math>9</math>
|<math>12</math>
|<math>3</math>
|<math>4</math>
!<math>1</math>
|<math>10</math>
|<math>9</math>
|<math>12</math>
|<math>3</math>
|<math>4</math>
!|<math>1</math>
|-
!<math>11</math>
|<math>11</math>
|<math>4</math>
|<math>5</math>
|<math>3</math>
|<math>7</math>
|<math>12</math>
|<math>2</math>
|<math>9</math>
|<math>8</math>
|<math>10</math>
|<math>6</math>
!|<math>1</math>
|-
!<math>12</math>
|<math>12</math>
!<math>1</math>
|<math>12</math>
!<math>1</math>
|<math>12</math>
!<math>1</math>
|<math>12</math>
!<math>1</math>
|<math>12</math>
!<math>1</math>
|<math>12</math>
!<math>1</math>
|}

== オイラーの定理 ==
{{main|オイラーの定理 (数論)}}
後になって[[レオンハルト・オイラー]]はこの定理を拡張し、 <math>a</math> を <math>n</math> と[[互いに素 (整数論)|互いに素]]な整数とすると、

:<math>a^{\varphi(n)}\equiv 1\pmod{n}</math>

が成り立つことを示した。ここで、<math>\varphi(n)</math> は <math>n</math> 以下の <math>n</math> と互いに素な自然数の個数を表し、''[[オイラー関数]]''と呼ばれる。

特に <math>n</math> が素数のときは、<math>\varphi(n)=n-1</math> より、フェルマーの小定理に一致する。

== カーマイケルの定理 ==
<math>m=\varphi(n)</math> とすれば、 <math>a^{m}\equiv 1\pmod{n}</math> が <math>n</math> と互いに素なすべての <math>a</math> に対して成り立つが、 <math>\varphi(n)</math> はこの性質を満たす <math>m</math> の最小の数とは限らない。カーマイケルの定理はオイラーの定理を精緻化したもので、すべての <math>a</math> に対して<math>a^{m}\equiv 1\pmod{n}</math>が成立するような最小の <math>m</math> を与える。ただし、<math>n</math> と互いに素な<math>a</math>が与えられたときに、 <math>a^{m}\equiv 1\pmod{n}</math> を満たす最小の<math>m</math>は、<math>\lambda \left( n\right)</math> となるとは限らない。

たとえば、<math>n=10000</math> のとき、カーマイケルの定理によれば <math>n</math> と互いに素なすべての <math>a</math>に対して <math>a^{m}\equiv 1\pmod{n}</math> を満たす最小の <math>m</math> は500であるが、特定の <math>a=7</math> に対しては <math>7^{100}\equiv 1\pmod{n}</math>　が成立する。

{{仮リンク|カーマイケル関数|en|Carmichael function}} <math>\lambda \left( n\right)</math> を以下のように再帰的に定義する。

<math>n=2^{e}</math> なら、
:<math>\lambda (2^e )=\begin{cases}
1 &(e=1)\\
2 &(e=2)\\
2^{e-2} &(e \ge 3)
\end{cases}</math>
<math>n</math> が奇素数 <math>p</math> を用いて <math>n=p^{e}</math> と書けるなら、
:<math>\lambda(p^e) = p^{e-1}(p-1)</math>

<math>n</math> が <math>p_{1}^{e_{1}}\ldots p_{k}^{e_{k}}</math> と[[素因数分解]]できるなら、
:<math>\lambda(p_1^{e_1} \dotsb p_k^{e_k}) = \operatorname{lcm} \{ \lambda(p_1^{e_1}), \dotsc, \lambda(p_k^{e_k}) \}</math>

ここで <math>\operatorname{lcm}</math> は[[最小公倍数]]。 

カーマイケルの定理は、 <math>a</math> と <math>n</math> が互いに素なとき、
:<math>a^{\lambda \left( n\right)}\equiv 1\pmod{n}</math>
が成り立つという定理である。

<math>\lambda \left( n\right)</math> が <math>n-1</math> の約数であるとき、 <math>n</math> は[[カーマイケル数]]と呼ばれ、自身と互いに素であるようなすべての底で[[#フェルマーテスト|フェルマーテスト]]を通過する絶対擬素数となる。

== フェルマーテスト ==
'''フェルマーテスト'''は、フェルマーの小定理の[[対偶 (論理学)|対偶]]を用いて[[素数判定|確率的素数判定]]を行う[[アルゴリズム]]である。

フェルマーの小定理の[[対偶 (論理学)|対偶]]をとると、これは次のように、自然数 ''n'' が[[合成数]]であるための十分条件を与える。
;対偶
:<math>n</math> と互いに素な整数 <math>a</math> が 
::<math>a^{n-1} \not\equiv 1\pmod{n}</math>
:を満たせば、 <math>n</math> は合成数である。
この十分条件を用いて、次のように自然数 <math>n</math> の素数判定を行う。
#パラメータとして、 <math>2</math> 以上 <math>n</math> 未満の自然数 <math>a</math> を1つ定める。
#<math>a</math> と <math>n</math> が互いに素でなければ「 <math>n</math> は合成数」と出力して終了。
#<math>a^{n-1} \not\equiv 1\pmod{n}</math> ならば「 <math>n</math> は合成数」と出力して終了する。そうでないとき「 <math>n</math> は確率的素数」と出力して終了する。
フェルマーテストが「合成数」と出力したとき、上のフェルマーの小定理の対偶によって <math>n</math> は実際に合成数である。しかし、上の対偶は十分条件を与えるのみで必要条件を与えるものではないので、「確率的素数」と出力された場合でも <math>n</math> は実際に素数であるとは限らない。素数ではないにもかかわらず「確率的素数」と判定されてしまう合成数は'''擬素数'''と呼ばれる。

疑わしければ、「確率的素数」と出力された場合にはまた異なる <math>a</math> を用いて再びテストを行う。十分な回数だけ <math>a</math> を取り替えて繰り返せば、フェルマーテストが「確率的素数」と判定した数は実際に素数である可能性が高い。

しかし、[[カーマイケル数]]または絶対擬素数と呼ばれる "反例" もある。カーマイケル数は合成数であるにもかかわらず、ほとんどいかなる <math>a</math> を用いても「確率的素数」と判定されてしまう。従って、フェルマーテストは完全な素数判定法ではない。

フェルマーテストを改善するアルゴリズムとしては、[[ミラー–ラビン素数判定法]]や[[AKS素数判定法]]がある。

== 一般化 ==
フェルマーの小定理・オイラーの定理は一般の[[有限群]]の定理に拡張できる。 <math>G</math> を[[位数 (群論)|位数]] <math>m</math> の有限群とすると、 <math>G</math> の任意の元 <math>g</math> に対して <math>g^{m}</math> は単位元に一致する。オイラーの定理は <math>G</math> が[[乗法群]] <math>\left( \mathbb{Z}/n\mathbb{Z}\right)^{\times}</math> のときの場合であり、フェルマーの小定理はさらに <math>n</math> が素数の場合である。

== 参考文献 ==
*{{Cite book|和書|author=高木貞治|authorlink=高木貞治|year=1971|month=|title=初等整数論講義|edition=第2版|publisher=[[共立出版]]|pages=67,53-54|isbn=4-320-01001-9|ref={{Harvid|高木|1971}}}}
*{{Cite book|和書|author=G.H.ハーディ|authorlink=ゴッドフレイ・ハロルド・ハーディ|coauthors=[[E・M・ライト]]|others=[[示野信一]]・[[矢神毅]] 訳|year=2001|month=7|title=数論入門I|publisher=[[シュプリンガー・フェアラーク東京]]|series=シュプリンガー数学クラシックス8 |pages=82-107|isbn=4-431-70848-0 |ref={{Harvid|ハーディ|ライト|2001a}}}}
**{{Cite book|和書|author=G・H・ハーディ|coauthors=E・M・ライト|others=示野信一・矢神毅 訳|year=2001|month=7|title=数論入門I|publisher=丸善出版|series=シュプリンガー数学クラシックス8 |url=http://pub.maruzen.co.jp/book_magazine/book_data/search/9784621062265.html|pages=82-107|isbn=978-4-621-06226-5 |ref={{Harvid|ハーディ|ライト|2001b}}}}

== 外部リンク ==
*{{高校数学の美しい物語|680|フェルマーの小定理の証明と例題}}
*{{MathWorld|title=Fermat's Little Theorem|urlname=FermatsLittleTheorem}}
*{{MathWorld|title=Euler's Totient Theorem|urlname=EulersTotientTheorem}}
*{{MathWorld|title=Carmichael's Theorem|urlname=CarmichaelsTheorem}}

{{DEFAULTSORT:ふえるまあのしようていり}}
[[Category:数論の定理]]
[[Category:ピエール・ド・フェルマー]]
[[Category:ゴットフリート・ライプニッツ]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]