このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

フェルマーの小定理の拡張定理

 フェルマーはフレニクルに次の結果を知らせた。これはフェルマーの小定理よりよい結果である。

[定理]
p:素数、a:pの倍数でない整数とする。
このとき、a^n~\equiv~1~\,~\pmod{p}となるような最小の整数n(>0)を取る。
すると、a^m~\equiv~1~\,~\pmod{p}となるような整数m(>0)は、nの倍数である。

 フェルマーの小定理より、nは存在し、n≦p-1を満たす。

[証明]a,a2,…を考え、最初にa^n~\equiv~1~\,~\pmod{p}となるnを取る。

また、m(>0)をa^m~\equiv~1~\,~\pmod{p}となるような整数とする。

mをnで割り、商をq、余りをrとすると、次が成り立つ。

m=qn+r,~0~\le~r~<~n

ここで、r>0と仮定すると、次のように展開が行える。

1
\equiv~a^m~\,~\pmod{p}
=~a^{qn+r}
=~(a^n)^q~a^r
\equiv~1^q~a^r (∵a^n~\equiv~1~\,~\pmod{p}
=a^r

nより小さいrに対して、a^r~\equiv~1~\,~\pmod{p}となってしまい矛盾する。

ゆえに、r=0である。即ち、n|mである。 □

[補講]フェルマーはこの定理を用いて、メルセンヌ数237-1が素数ではないことを証明した。

237-1=137438953471を、アルキメデスの篩によって素数かどうかを調べるのは大変である。

そこで、237-1を割り切る素数をpとする。即ち、次が成り立つ。

2^{37}~\equiv~1~\,~\pmod{p}

上記定理において、a=2とする。すると、2^n~\equiv~1~\,~\pmod{p}となる最小のn(>0)を取れば、37はnの倍数でなければならない。即ち、n|37である。
37は素数なので、n=37である。

また、フェルマーの小定理より、m=p-1とおける。
すると、37|p-1が成り立つ。
即ち、pは37l+1の形の素数でなければならない。

さらに、pが奇数であるため、偶数lだけを考えればよい。
つまり、l=2kとして、p=74k+1の形の素数でなければならない。

これで、370727以下のすべての素数ではなく、上記の形を満たす限られた素数が、237-1を割り切るかどうかを調べればよい。

  • k=1の場合、即ちp=75の場合
    • このpは素数ではない。
  • k=2の場合、p=149の場合
    • pは素数だが、237-1を割り切らない。
  • k=3の場合、p=223の場合
    • pは素数であり、237-1=223×61631877と割り切れる。

よって、3回目の計算ですでに、割り切る値が登場した。
つまり、メルセンヌ数237-1は素数ではない。 ◇

[系]p:素数、a:pの倍数でない整数とする。
このとき、a^n~\equiv~1~\,~\pmod{p}となるような最小の整数n(>0)を取る。
すると、n|p-1が成り立つ。

[証明]フェルマーの小定理より、a^{p-1}~\equiv~1~\,~\pmod{p}なので、上記の定理でm=p-1とおける。
ゆえに、n|p-1が成り立つ。 □

参考文献

  • 『なっとくするオイラーとフェルマー』