📂整数論

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

定理 ¹

素数 $p$ とそれと互いに素な整数 $a$ について、$a^{p-1} \equiv 1 \pmod{p}$

説明

フェルマーの小定理は、シンプルでありながら非常に多くの場所で利用される定理の一つである。オイラーによって一般化された定理もあるが、フェルマーの小定理だけで十分な場合も多い。特に有限体でのべき乗を多く扱う暗号理論などでは、不可欠な定理である。

証明

戦略: 証明はシンプルだが、それほど簡単ではない。もし $$ a \cdot 2a \cdot \cdots \cdot (p-1)a \equiv (p-1)! \pmod{p} $$ が成立するなら、両辺から$(p-1)!$を消去してフェルマーの小定理を証明することができるだろう。つまり、二つの集合$\left\{ a,2a,\cdots , (p-1)a \right\}$ と $\left\{1,2,\cdots ,(p-1) \right\}$ が$\pmod{p}$で同じであることを示せばよい。

---

集合 $\left\{ a,2a,\cdots , (p-1)a \right\}$ は、有限集合であるとして、正確に$(p-1)$個の要素を持つ。$a$が$p$と互いに素であるため、これらの要素を$p$で割った余りは$1$から$(p-1)$までの整数のいずれかになるだろう。そして、その余りに重複がなければ、 $$ \left\{ a,2a,\cdots , (p-1)a \right\} = \left\{1,2,\cdots ,(p-1) \right\} $$ が成立するだろう。$\left\{ a,2a,\cdots , (p-1)a \right\}$から異なる任意の二つの要素$ia$と$ja$を取り出して考えてみる。これらを$p$で割った余りが同じと仮定すると、$ia \equiv ja \pmod{p}$が成立する。$a$が$p$と互いに素であるため、両辺から$a$を消去すると、$i \equiv j \pmod{p}$も成立する。しかし、上記の集合で$i$と$j$は$0$より大きく$p$より小さい整数だったため、$ia$と$ja$も同じである。これは仮定に反するので、異なる任意の二つの要素を$p$で割った余りは常に異なると言える。余りに重複がないため$\pmod{p}$で、 $$ \left\{ a,2a,\cdots , (p-1)a \right\} = \left\{1,2,\cdots ,(p-1) \right\} $$ が成立する。一方で$p$は素数であるため、$(p-1)!$と互いに素である。 $$ (p-1)! a^{p-1} \equiv (p-1)! \pmod{p} $$ 両辺から$(p-1)!$を消去すると、合同式$a^{p-1} \equiv 1 \pmod{p}$を得る。

■

以下の系も覚えておくと良い。

系

• [1] 逆元: $\pmod{p}$で、乗算に対する$a$の逆元は必ずこのように与えられる。 $$ a^{-1} \equiv a^{p-2} \pmod{p} $$
• [2] フェルマーのテスト: $a^n \equiv a \pmod{n}$が成立しない場合、$n$は合成数である。

ある数が素数かどうかを判定することは難しいが、合成数であることは比較的判定しやすい。注意すべきは、フェルマーのテストの逆は成立しないということである。特に逆が成立しないことを示す反例としては、カーマイケル数がある。カーマイケル数の例として$561=3 \cdot 11 \cdot 17$は合成数だが、$a^{561} \equiv a \pmod{561}$は常に成立する。

コード

以下は、Rでフェルマーテストを実装したもので、計算には連続べき乗法が使用された。

FPM<-function(base,power,mod) #It is equal to (base^power)%%mod
{
  i<-0
  if (power<0) {
    while((base*i)%%mod != 1) {i=i+1}
    base<-i
    power<-(-power)}
  
  if (power==0) {return(1)}
  if (power==1) {return(base%%mod)}
  
  n<-0
  while(power>=2^n) {n=n+1}
  
  A<-rep(1,n)
  A[1]=base
  
  for(i in 1:(n-1)) {A[i+1]=(A[i]^2)%%mod}
  
  for(i in n:1) {
    if(power>=2^(i-1)) {power=power-2^(i-1)}
    else {A[i]=1} }
  
  for(i in 2:n) {A[1]=(A[1]*A[i])%%mod}
  
  return(A[1])
}
 
fermat.test<-function(n)
{
  for(i in 2:(n-1))  {if( i!=FPM(i,n,n) ) {return(paste(i,"is a Fermat witness!"))}}
  paste(n,"passes the Fermat test!")
}
 
fermat.test(121)
fermat.test(341)    #Almost composite yields fermat witness 2, but 341=11*31 doesn't.
fermat.test(561)    #Carmicheal number 561 = 3*11*17
fermat.test(1031)    #1031 is a prime
fermat.test(1105)    #Carmicheal number 1105 = 5*13*17
fermat.test(1729)    #Carmicheal number 1729 = 7*13*19
fermat.test(41041)    #Carmicheal number 41041 = 7*11*13*41

以下はコードを実行した結果である。

フェルマーテストは$121$や$341$のような合成数を確実に捕捉でき、$1031$のような素数を正しく通過させた。しかし、$561$、$1105$、$1729$、$41041$のようなカーマイケル数は捕捉できなかった。カーマイケル数を捕捉するには、ミラー-ラビンテストのような方法を使う必要がある。