■フェルマー商(その2)

 フェルマー商

  (2^(p-1)−1)/p

が整数になる(2^(p-1)−1がpで割り切れる)のに,pが素数でない場合,pを擬素数(プーレ数)という.

 2^340−1は341で割り切れるのみ,341=11・13は合成数であり,素数ではない.341は2を底とする最小の擬素数である.

===================================

【1】擬素数

 たとえば,

  n|2^n−2

において,n=5のとき2^5−2=30は5で割り切れるが,n=15のとき2^15−2=32766は15で割り切れない.

 フェルマーの定理「aが素数pと公約数をもたないならば,a^p-1−1はpで割り切れる」は,記号

  (a,p)=1→p|a^p-1−1

を用いて表される.

 しかし,フェルマーの定理の逆は真ではない.n=341=11・31のとき,2^341−2は341で割り切れる.nが素数のときかつそのときに限って

  n|2^n−2,2^n=2  (modn)

は「・・・のとき」は正しいが,「かつそのときに限って」は誤っている.

 nが奇数のとき

  2^n-1=1  (modn)

と書いてもよい.

  2^340=1  (mod341)

であることを実際に確かめてみよう.

  2^10=1024=1  (mod341)

  2^340=(2^10)^34=1  (mod341)

 341は2を底とする擬素数と呼ばれる.もっと一般に

  a^n-1=1  (modn)

が成り立つ奇数の合成数であると定義される.

 341は2を底とする最小の擬素数であるから,逆にいえば,nが341より小さい奇数のとき,nが素数でないならば2^n−2はnで割り切れないことになる.

  2^340=1  (mod341)

であったが,2^170  (mod341)は+1か−1か?

  2^170=(2^10)^17=1  (mod341)

それでは,2^85  (mod341)は?

  2^170=2^5(2^10)^17=32  (mod341)

 645は2を底とする2番目の擬素数.1105,1387,1905,・・・と続く.なお,擬素数は素数の数よりも稀であるが,にもかかわらず,無限に存在する.

 1610380は2を底とする偶数の擬素数,2番目は215326.偶数の擬素数は無限に存在することが証明されている.

 91は3を底とする最小の擬素数.

 15は4を底とする最小の擬素数.2番目は217.

===================================

【2】完全擬素数(カーマイケル数)

 341は2を底とする最小の擬素数であったが,どんな底に対しても

  a^p−a

がpで割り切れるとき,pを完全擬素数(カーマイケル数)という.

 561は最小の完全擬素数であて,以下,

  1105,1729,2465,2821,6601,8911,10585,・・・

と続く.無限に存在すると信じられているが,証明されていない.

 どのカーマイケル数も少なくとも3つの素因数を含む.

===================================

【3】超プーレ数

 どの約数dに対しても,2^d−2がdで割り切れる数を超プーレ数という.2047は超プーレ数である.超プーレ数はすべて奇数である.

===================================