■整数であるか? (その23)
341=11・13は合成数であり,素数ではない.フェルマーの小定理の逆は成り立たない.フェルマー商
(2^(p-1)−1)/p
が整数になる(2^(p-1)−1がpで割り切れる)のに,pが素数でない場合,pを擬素数という.
2^340−1は341で割り切れる.341は2を底とする最小の擬素数である.
===================================
2^340=1 (mod341)
であることを実際に確かめてみよう.
2^10=1024=1 (mod341)
2^340=(2^10)^34=1 (mod341)
2^340 (mod341)
を計算するにあたり、
2^10=1024=1 (mod341)
が成り立つことは運がよかったといえるが、一般にはそんなに運がいいとは限らない。
===================================
2^340=1 (mod341)
であったが,2^170 (mod341)は+1か−1か?
2^170=(2^10)^17=1 (mod341)
それでは,2^85 (mod341)は?
2^85=2^5(2^10)^8=32 (mod341)
===================================