横画面推奨!
モバイル機器の場合、数式が見切れる場合があります。

2024年3月31日

なぜ素数であるかを平方根以下の素数を約数としてもつかで判定できるのか?

 自然数nが素数であるかはなぜn以下の素数を約数としてもつかどうかで判定できるのでしょうか?


 素数は1と自分自身しか約数としてもたないため、自然数nが素数であるかを確かめるにはn未満の約数が1以外にないことを示す必要があります。
そのために以下のことについて考えます。
 正の実数x,yについてxy=nn:自然数)が成り立つとき、x+yの値について考えます。
相加平均と相乗平均の大小関係より
x+y2xy=2n
で等号成立条件はx=yであることがわかります。
xy=nよりx=yのときのそれぞれの値はx=y=nだけであることがわかります。
さらに、xyの場合についても調べてみます。
xの値について0<x<n,x>nの2つの場合があるので、それぞれのときのyの値について調べると
xy=nよりy=nx

0<x<nのとき

0<x<nならば1x>1nなので
nx>nny>n

x>nのとき

x>nならば0<1x<1nなので
0<nx<nn0<y<n
以上よりxy=nを満たす正の実数x,yについて
  1. x=yとなるのはx=y=nのときだけである。
  2. xyならば必ずx,yの一方はnより大きく、もう一方はnより小さい。
ということがわかります。
これはnは必ずn以下の正の約数とn以上の正の約数の積で表せるということです。(nの自明な約数には1,nがありn=1nとなるので、これが自明なn以下の正の約数とn以上の正の約数の積となります。)
このことから、1以外のn以下の正の約数が存在するならばn以外のn以上の正の約数が存在するということがいえます。
ところで、自然数は必ず自身以下の素数を約数にもちます。また、整数nの約数aの約数bnの約数でもあります。
すなわち、1以外のn以下のnの正の約数が存在するならば必ずnとの公約数であるn以下の素数が存在するので、1以外のn以下のnの正の約数が存在するかを知るにはnn以下の素数を約数としてもつかを調べればよいことがわかります。
調べた結果nがどのn以下の素数も約数としてもたないことが示されれば、それはn以下のnの正の約数が1以外にないということであり、連鎖的にn以上のnの正の約数もn以外にないことがわかるので、nは素数であると判定できます。

 ちなみにnn以上の素数を約数としてもつかを調べることでnが素数であるかを判定できないのかと思うかもしれませんが、必ずしも判定できるわけではありません。
例えば12が素数かを判定してみると、123.5以上12未満の素数5,7,11のいずれかを約数にもつかを調べてみるとどれも約数にもちません。
だから12は素数であるいえるかというとそうではなく、実際は12=22×3と素因数分解できる合成数です。
このようにn以下の素数しか約数に持たない数が存在するのでn以上の素数から素数判定をすることはできません。

また、n以外のn以上のnの正の約数を探す方法についても、1からnまでの範囲の幅がn1であるのに対してnからnまでの範囲の幅はnn=n(n1)n倍あり、1以外のn以下のnの正の約数を探すほうが範囲が狭く簡単なので効率的な方法であるとはいえません。

この素数判定法はn以下のnの素因数を探す方法でもあるので、素因数分解のときにも役立ちます。


Share:
share
◎Amazonのアソシエイトとして、当サイト「数学について考えてみる」は適格販売により収入を得ています。
Powered by Blogger.

PR

blogmura_pvcount
ブログランキング・にほんブログ村へ