素数 – 判定：人力で判定するやり方を実演【３桁くらいなら楽勝】
“素数 – 判定 “について、エラトステネスのふるい （篩）を算数で学習した内容から少し工夫をします。
すると、1万以下の自然数くらいだと、人力で素数かどうかを判断できるようになります。
例えば、503 が素数かどうかということを判定することができます。
3 ケタや 4 ケタの整数について、約数が 1 とその数以外にあるかどうかを効率的に判断できる方法になります。
エラトステネスのふるいを学習し、ある程度２ケタの素数を知っている方だと３ケタくらいの判定は問題冊子の余白で十分に素数判定を行えます。
素数とは、2 以上の自然数で、約数が 1 とその数自身しかない自然数のことです。
別の言い方をすると、正の約数が 2 個しかない自然数を素数といいます。
例えば、5 だと正の約数が 1 と 5 の 2 個しかないので素数です。
2 も同じく正の約数が 2 個しかないので素数です。
しかし、1 は正の約数が 1 個しかないので素数ではありません。
この素数の簡単な見分け方をこれから解説します。
先ほどの素数の定義に基づいて、11 くらいの小さな整数だと素数かどうかをエラトステネスのふるいの直接計算で確かめられます。
しかし、503 くらいになってくると、約数かどうかを判断する自然数が多くなり大変になります。
そこで、素数判定を行う方法がないかと思うわけです。
実は、3 ケタや 4 ケタくらいなら、人力の手計算で素数かどうかを判定する方法があります。
まず、その判定のやり方を述べます。
根拠となる整数分野の数学の定理は記事の最後で証明することにします。
素数-判定-やり方
【実行手順】
自然数 n が素数かどうかを以下の手順で調べる。
[1] n にルートをつけ小数で近似
[2] 近似した小数を超えない最大の整数を t とする。
[3] この t の値以下のすべての素数で割り切れなければ、n は素数。
※ １つでも割り切る素数があれば、n は素数でない。
この【定理】は古典的な整数論において知られたものです。
※ 手順[2]は、ガウス記号をとったということです。
ただ、ガウス記号という数学の内容を知らなくても、この手順の通りに進めると素数判定を行うことができます。
試験中に少しの労力で人力で行える内容のレベルとして、３ケタくらいの自然数について判断できるようになれば幸いです。
17で実演
17 という自然数が素数かどうかを判定します。
手順[1]により、17 にルートをつけます。
電卓があると、
17 にルートをつけると、
4.1231・・・
となることが、すぐにわかります。
手順[2]によって、この小数点以下をすべて切り捨てることになります。
そのため、手順[2]の t は 4 ということになります。
※ ガウス記号の意味は、負の整数のときに小数点以下の切り捨てとは異なりますが、今は正の自然数だけの議論なので、[2]では結果的に小数点以下の切り捨てということになります。
これで手順[3]の実行です。
t = 4 なので、4 以下のすべての素数で割り切れるかどうかを調べることになります。
4 以下の素数は 2 と 3 です。
17 は 2 でも 3 でも割り切れません。
これで、17 は素数と判断できました。
ルートが絡みましたが、中学数学をまだ学習していない方は、
手順[1]と[2]を次のように嚙み砕いておくと、算数レベルで判定できます。
同じ数 2 個で掛け算を計算することを二乗するといいます。
4 × 4 < 17 < 5 × 5 です。
これで、
17 にルートをつけると、
4 より大きく 5 よりも小さいということが分かります。
そのため、17 にルートをつけた数を越えない最大の整数は 4 ということになります。
これで、[3] の手順を実行するわけです。
[3] にあたっては、小学校で鍛えた九九の唱和とエラトステネスのふるいの勉強で既に知っている２ケタの素数が役に立ちます。
素数でないときの例
38 が素数かどうかを判定してみます。
まず手順[1]により、38 にルートをつけます。
6 × 6 < 38 < 7 × 7 なので、
38 にルートをつけた値は、
6 より大きく 7 より小さい数ということになります。
よって、手順[2] の 38 にルートをつけた数を越えない最大の整数は 6 です。
※ 小数点以下を切り捨てるので 6 となります。
これで、t = 6 と分かったので、手順[3]を実行します。
t = 6 以下の素数は、2, 3, 5 です。
3 や 5 では 38 を割り切ることができません。
しかし、2 は 38 を割り切ります。
したがって、38 は素数でないと判断されました。
このように、手順[3]で、t 以下の素数を全て調べることになるので、3ケタの自然数が素数かどうかを判定する前段階として、2ケタの素数をまとめておきます。
実演した要領で、100以下の素数を調べると次のようになります。
100以下の素数判定のまとめ
【50以下の素数】
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 が素数です。
全部で 15 個です。
50 の二乗は 2500 なので、
2500 以下の自然数については、これらの 15 個の素数すべてで割り切れないかどうかで判断できます。
100 の二乗は 10000 なので、10000 以下の自然数の素数判定のために、51 以上 100 以下の範囲にある素数もまとめておきます。
【51 以上 100 以下の素数】
53, 59, 61, 67, 71, 73, 79, 83, 89, 97 が素数です。
全部で 10 個です。
10000 以下の自然数については、
これら 25 個の素数すべてで割り切れなければ、素数です。
これらのまとめは、手順[3]を円滑に実行するための準備となります。
では、3ケタの素数についても練習してみます。
目標503で素数判定
503 が素数かどうかを手順に基づいて調べます。
22 × 22 < 503 < 23 × 23
これで、
手順[1]で503にルートをつけると、
22 より大きく 23 より小さい数だと分かります。
そのため、
手順[2]で503にルートをつけた数を越えない最大の整数は、
22 ということになります。
つまり、t = 22 です。
最後に手順[3]により、
22 以下の素数で、503 が割り切れるかどうかを確認することになります。
22 以下の素数は
2, 3, 5, 7, 11, 13, 17, 19 です。
2 と 3 と 5 と 7 が 503 を割り切らないことは暗算で計算できます。
ですので、11 と 13 と 17 と 19 に絞って、
503 を割り切るかどうかを確認します。
503 = 11 × 45 + 8,
503 = 13 × 38 + 9,
503 = 17 × 29 + 10,
503 = 19 × 26 + 9
これで、503 は 22 以下のすべての素数で割り切れないことが確認できました。
503 は素数と判定できました。
最後に分数の約分に応用してみます。
157/191が約分できるか
157 / 191 について、分子と分母の公約数で 2 以上のものがあれば、約分できますが、どうでしょうか？
大学受験の記述答案だと、マークの形がないので、約分ができるのか焦るかもしれません。
旧課程の高校数学では、整数単元でユークリッドの互除法を学習していたので、最大公約数を求めることができました。
しかし、最大公約数の求め方を知らないという方は、なかなか約数が見つからないときに、素数という可能性を調べてみるのも良いかと思います。
分母を調べてみます。
132 < 191 < 142より、
t = 13 だから、
13 以下の素数を手順[3]によって調べることになります。
2, 3, 5, 7, 11, 13 が該当する候補です。
191 は一の位を見ると奇数なので、奇数だから 2 で割り切れません。
したがって、
3, 5, 7, 11, 13 について割り切れるかどうかを確認します。
191 = 3 × 63 + 2,
191 = 5 × 38 + 1,
191 = 7 × 27 + 2,
191 = 11 × 17 + 4,
191 = 13 × 14 + 9,
191 は 13 以下のすべての素数で割り切れなかったので、
191 は素数です。
そのため、191 の正の約数は 1 と 191 のみです。
分子の 157 は 191 より小さいので、
191 では割り切れません。
よって、分子の 157 と分母の 191 の最大公約数が 1 なので、これ以上は約分できないということが分かりました。
ここまで、素数かどうかの判定を人力で行うための手順を使ってきました。
この手順には、整数分野のおおもとの【定理】があります。
その【定理】を高校の数学で学習をする背理法を使って証明しておきます。
素数-判定:根拠となる【定理】の証明
＜証明＞
この k が素数でないと仮定します。
すると、2 以上 k － 1 以下の範囲にある自然数 a, b が存在して、
k = ab と表すことができます。
仮定より a と b は z より大きい自然数なので、
k < (z + 1)(z + 1) ≦ ab = k となります。
つまり、k < k ということなので、矛盾です。
よって、背理法から k は素数ということになります。【証明完了】
注意点
今回の【定理】の証明で、その値を越えない最大の整数ということの意味が鍵となっていました。
この内容は、整数の問題で、たびたび出てくるので、論理的にまとめておきます。
整数 z が 実数 x を越えない最大の整数とすると、
越えないわけですから z ≦ x ということになります。
ここで、z + 1 も整数です。
大小関係について、
z + 1 > x, z + 1 = x,
z + 1 < x の 3 通りが考えられます。
しかし、z + 1 ≦ x とすると、
z < z + 1 ですから、z が x を越えない最大の整数ということに矛盾してしまいます。
そのため、必ず z + 1 > x となります。
よって、z が x を越えない最大の整数ということは、
z ≦ x < z + 1 ということになります。
ちなみに、実数 x を越えない最大の整数のことを
[x] と表すときがあります。
この記号をガウス記号といいます。
【関連する整数記事】
■ 中国剰余定理
■ 5進数の小数
それでは、これで今回の記事を終了します。
読んで頂き、ありがとうございました。