自然数が素数であるかはなぜ以下の素数を約数としてもつかどうかで判定できるのでしょうか?
素数はと自分自身しか約数としてもたないため、自然数が素数であるかを確かめるには未満の約数が以外にないことを示す必要があります。
そのために以下のことについて考えます。
正の実数について(自然数)が成り立つとき、の値について考えます。
相加平均と相乗平均の大小関係より
で等号成立条件はであることがわかります。
よりのときのそれぞれの値はだけであることがわかります。
さらに、の場合についても調べてみます。
の値についての2つの場合があるので、それぞれのときのの値について調べると
の値についての2つの場合があるので、それぞれのときのの値について調べると
より
のとき
ならばなので
のとき
ならばなので
以上よりを満たす正の実数について
ということがわかります。
- となるのはのときだけである。
- ならば必ずの一方はより大きく、もう一方はより小さい。
これはは必ず以下の正の約数と以上の正の約数の積で表せるということです。(の自明な約数にはがありとなるので、これが自明な以下の正の約数と以上の正の約数の積となります。)
このことから、以外の以下の正の約数が存在するならば以外の以上の正の約数が存在するということがいえます。
このことから、以外の以下の正の約数が存在するならば以外の以上の正の約数が存在するということがいえます。
ところで、自然数は必ず自身以下の素数を約数にもちます。また、整数の約数の約数はの約数でもあります。
すなわち、以外の以下のの正の約数が存在するならば必ずとの公約数である以下の素数が存在するので、以外の以下のの正の約数が存在するかを知るにはが以下の素数を約数としてもつかを調べればよいことがわかります。
すなわち、以外の以下のの正の約数が存在するならば必ずとの公約数である以下の素数が存在するので、以外の以下のの正の約数が存在するかを知るにはが以下の素数を約数としてもつかを調べればよいことがわかります。
調べた結果がどの以下の素数も約数としてもたないことが示されれば、それは以下のの正の約数が以外にないということであり、連鎖的に以上のの正の約数も以外にないことがわかるので、は素数であると判定できます。
ちなみにが以上の素数を約数としてもつかを調べることでが素数であるかを判定できないのかと思うかもしれませんが、必ずしも判定できるわけではありません。
例えばが素数かを判定してみると、以上未満の素数のいずれかを約数にもつかを調べてみるとどれも約数にもちません。
だからは素数であるいえるかというとそうではなく、実際はと素因数分解できる合成数です。
このように以下の素数しか約数に持たない数が存在するので以上の素数から素数判定をすることはできません。
例えばが素数かを判定してみると、以上未満の素数のいずれかを約数にもつかを調べてみるとどれも約数にもちません。
だからは素数であるいえるかというとそうではなく、実際はと素因数分解できる合成数です。
このように以下の素数しか約数に持たない数が存在するので以上の素数から素数判定をすることはできません。
また、以外の以上のの正の約数を探す方法についても、からまでの範囲の幅がであるのに対してからまでの範囲の幅はで倍あり、以外の以下のの正の約数を探すほうが範囲が狭く簡単なので効率的な方法であるとはいえません。
この素数判定法は以下のの素因数を探す方法でもあるので、素因数分解のときにも役立ちます。
Share: