📂整数論

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

定理¹

素数$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$のようなカーマイケル数は捕らえることができなかった。カーマイケル数を捕らえるには、ミラー・ラビン判定法のような方法を用いなければならない。