■擬素数の望ましくない性質

【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)

 なお,擬素数は素数の数よりも稀であるが,にもかかわらず,無限に存在する.

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

【2】分割数

 ラマヌジャンはp(n)が満たす合同式について

  p(5n+4)=0  mod5

  p(7n+5)=0  mod7

  p(11n+6)=0  mod11

  p(599)=0  mod5^3

  p(721)=0  mod11^2

を予想し,それらを証明しています.

 さらに,

  d=5^a7^b11^c かつ 24n=1  (mod d)

ならば,

  p(n)=0  (mod d)

を予想していますが,n=243の場合,

  p(243)=133978259344888

は,24・243=1  (mod 343)であるにもかかわらず,d=7^3=343では割り切れない.

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