自然数$n$が素数であるかはなぜ$\sqrt{n}$以下の素数を約数としてもつかどうかで判定できるのでしょうか？
素数は$1$と自分自身しか約数としてもたないため、自然数$n$が素数であるかを確かめるには$n$未満の約数が$1$以外にないことを示す必要があります。
そのために以下のことについて考えます。
正の実数$x,y$について$xy=n$（$n:$自然数）が成り立つとき、$x+y$の値について考えます。
相加平均と相乗平均の大小関係より
\[x+y\geqq2\sqrt{xy}=2\sqrt{n}\]
で等号成立条件は$x=y$であることがわかります。
$xy=n$より$x=y$のときのそれぞれの値は$x=y=\sqrt{n}$だけであることがわかります。
さらに、$x\neq y$の場合についても調べてみます。
$x$の値について$0<x<\sqrt{n},x>\sqrt{n}$の2つの場合があるので、それぞれのときの$y$の値について調べると
$x$の値について$0<x<\sqrt{n},x>\sqrt{n}$の2つの場合があるので、それぞれのときの$y$の値について調べると
$xy=n$より$y=\dfrac{n}{x}$
$0<x<\sqrt{n}$のとき
$0<x<\sqrt{n}$ならば$\dfrac{1}{x}>\dfrac{1}{\sqrt{n}}$なので
\begin{align*}\frac{n}{x}&>\frac{n}{\sqrt{n}}\\[0.5em]\therefore
y&>\sqrt{n}\end{align*}
$x>\sqrt{n}$のとき
$x>\sqrt{n}$ならば$0<\dfrac{1}{x}<\dfrac{1}{\sqrt{n}}$なので
\begin{align*}0<&\frac{n}{x}<\frac{n}{\sqrt{n}}\\[0.5em]\therefore0<&y<\sqrt{n}\end{align*}
以上より$xy=n$を満たす正の実数$x,y$について
ということがわかります。
- $x=y$となるのは$x=y=\sqrt{n}$のときだけである。
- $x\neq y$ならば必ず$x,y$の一方は$\sqrt{n}$より大きく、もう一方は$\sqrt{n}$より小さい。
これは$n$は必ず$\sqrt{n}$以下の正の約数と$\sqrt{n}$以上の正の約数の積で表せるということです。（$n$の自明な約数には$1,n$があり$n=1\cdot
n$となるので、これが自明な$\sqrt{n}$以下の正の約数と$\sqrt{n}$以上の正の約数の積となります。）
このことから、$1$以外の$\sqrt{n}$以下の正の約数が存在するならば$n$以外の$\sqrt{n}$以上の正の約数が存在するということがいえます。
このことから、$1$以外の$\sqrt{n}$以下の正の約数が存在するならば$n$以外の$\sqrt{n}$以上の正の約数が存在するということがいえます。
ところで、自然数は必ず自身以下の素数を約数にもちます。また、整数$n$の約数$a$の約数$b$は$n$の約数でもあります。
すなわち、$1$以外の$\sqrt{n}$以下の$n$の正の約数が存在するならば必ず$n$との公約数である$\sqrt{n}$以下の素数が存在するので、$1$以外の$\sqrt{n}$以下の$n$の正の約数が存在するかを知るには$n$が$\sqrt{n}$以下の素数を約数としてもつかを調べればよいことがわかります。
すなわち、$1$以外の$\sqrt{n}$以下の$n$の正の約数が存在するならば必ず$n$との公約数である$\sqrt{n}$以下の素数が存在するので、$1$以外の$\sqrt{n}$以下の$n$の正の約数が存在するかを知るには$n$が$\sqrt{n}$以下の素数を約数としてもつかを調べればよいことがわかります。
調べた結果$n$がどの$\sqrt{n}$以下の素数も約数としてもたないことが示されれば、それは$\sqrt{n}$以下の$n$の正の約数が$1$以外にないということであり、連鎖的に$\sqrt{n}$以上の$n$の正の約数も$n$以外にないことがわかるので、$n$は素数であると判定できます。
ちなみに$n$が$\sqrt{n}$以上の素数を約数としてもつかを調べることで$n$が素数であるかを判定できないのかと思うかもしれませんが、必ずしも判定できるわけではありません。
例えば$12$が素数かを判定してみると、$\sqrt{12}≒3.5$以上$12$未満の素数$5,7,11$のいずれかを約数にもつかを調べてみるとどれも約数にもちません。
だから$12$は素数であるいえるかというとそうではなく、実際は$12=2^2×3$と素因数分解できる合成数です。
このように$\sqrt{n}$以下の素数しか約数に持たない数が存在するので$\sqrt{n}$以上の素数から素数判定をすることはできません。
例えば$12$が素数かを判定してみると、$\sqrt{12}≒3.5$以上$12$未満の素数$5,7,11$のいずれかを約数にもつかを調べてみるとどれも約数にもちません。
だから$12$は素数であるいえるかというとそうではなく、実際は$12=2^2×3$と素因数分解できる合成数です。
このように$\sqrt{n}$以下の素数しか約数に持たない数が存在するので$\sqrt{n}$以上の素数から素数判定をすることはできません。
また、$n$以外の$\sqrt{n}$以上の$n$の正の約数を探す方法についても、$1$から$\sqrt{n}$までの範囲の幅が$\sqrt{n}-1$であるのに対して$\sqrt{n}$から$n$までの範囲の幅は$n-\sqrt{n}=\sqrt{n}(\sqrt{n}-1)$で$\sqrt{n}$倍あり、$1$以外の$\sqrt{n}$以下の$n$の正の約数を探すほうが範囲が狭く簡単なので効率的な方法であるとはいえません。
この素数判定法は$\sqrt{n}$以下の$n$の素因数を探す方法でもあるので、素因数分解のときにも役立ちます。
Share:
