エラトステネスのふるい（素数）についての疑問

質問

今、家にある中学の参考書を読みながら、中学数学を勉強しているものです。その中の素数についての一番最初の問題で、

次のうちから、素数を選べ。
1　6　13　25　51　79　87　91

という問題があり、その解法の一つでエラトステネスのふるいというもの（2から順に自然数を書き、2を残して2の倍数を消し、3を残して3の倍数を消し、5を残して5の倍数を消す、以下同様にして求める…という方法）があるのですが、上の問題でずっとエラトステネスのふるいを使いながら合成数を消していくと、11の倍数を消すところで、「13、79は11で割り切れず、13÷11、79÷11ともに商が11より小さくなるから素数である。」と参考書にあり、そこでふるいをかける作業は終わっています。

この参考書（特に、"13÷11、79÷11ともに商が11より小さくなるから素数である。"というところ）のこの部分と、ずっとにらめっこをしてきたのですが、何故「13÷11、79÷11ともに商が11より小さくなるから素数である」と言い切れるのか、分かりませんでした…。

少なくとも13は、次に11の倍数となる数である11×2=22の間に13が存在しないから素数、と言い切れる感じはするのですが、79だと、たとえ11で割り切れなくても、13、17で割り切れるかもしれない…（もちろん実際そんなことはないのですが）、と、感覚的にそう思ってしまいます。そして、「13÷11、79÷11ともに商が11より小さくなるから素数である」を言いかえれば、「商が11より大きくなる場合は、素数でない可能性がある（121以降の数であれば、たとえ今の時点で11で割り切れなくても、素数でないかもしれない）」というのも、よく分かりません…。
そんなこんなで、このふるいが11で終わっている理由が分からないのです。

馬鹿みたいな問題かもしれないのですが、頭が堅くて、分からなくて困っているので、良かったら教えていただければ嬉しいです…。

回答No.4

masudaya · ベストアンサー

エラトステネスのふるい自体について説明をしておきます.
エラトステネスのふるいは,まず,1を消して2を残して2の倍数を消します.次に
(1)残っている最小の数を残してその数の倍数を消す.
この(1)を繰り返す,という素数を求める方法です.
これだと無限に繰り返さなければなりませんね.
たとえば,121までの素数を求める場合どのようにするかということを考えて見ましょう.(問題に合わせて121にしていますので,これはいくらでもいいのですが)121=11×11ですね.これより小さい数が素数でない場合,約数がどのようになるかが分かればいいわけです.(実際にはこの約数は11(:求めたい範囲の平方根)よりも小さいことになるのですが・・・)

121以下の整数が素因数分解できたとします.そのとき因数がp,qの二つであったとすると,p,qのいずれかは11よりも小さくなります.なぜなら両方とも11より大きければ,その数は,121より大きくなってしまいます.
∴p<11orq<11
つまり,121より小さい合成数(素数でないものをこういいます.)は必ず,11以下の因数を持っている.つまり,11以下の約数になるということです.逆に11までの約数を持たなければ,その数(121以下)が素数ということになります.
これを一般の場合にすると求める数の平方根を超えない最大の素数まで確認すれば,いいことを示すこともできるはずです.(この辺はご自身でどうぞ)

お礼

ようやく分かりました…！商のことを考えるには、素数にならない数のことを考えればよかったんですね。
私のような相手に、どうも有難うございました。

回答No.3

rmz1002

No.1です。

そーですね、今回も分かりやすく「221の場合」を考えてみましょう。
221を11で割ると、「商=20、余り=1」となり一見素数のように思えます。
しかし実際には「13でわると商=17、余り=0となる」ので「素数ではない」のです。
こーゆーのがあるから「素数ではないかもしれない」ということになります。
しかしこれはあくまで「11で割った商が11より大きい数（=11×11=121より大きい数）の場合」です。

問題に出ている数を見てみると「すべて121以下です」ので、そのような数を考える必要はありません。
だから「11まで考えればいい」ことになります。

お礼

すみません、やっと解決しました。
理解出来なくてすみませんでした。ですが、ご回答、どうもありがとうございました。

補足

本当にごめんなさい…まだ分からないです。

何故、11で割った商が11より大きい数（121以上）の場合は商を考える必要があるのかということと、問題になっている数は121以下だから、11までしか考えなくていいということ…何故そう言いきっていいのかが分からないんです。

言い換えれば、なんで13や79は11の倍数でないから、これ以上考えなくても良いのかが分からないんです。確かに下の方の回答の方法（平方根の大小で考える方法）で考えると納得できるのですが、商が11より大きい・小さいで考える方法ですと、やっぱり納得ができないんです…。

回答No.2

liar_adan

素数を調べる場合、平方根までを調べればいいのです。

仮に、ある数が素数でないとすれば、なにかの数の積として表すことができます。
数をxとすると、

x = a × b

となりますね。
この場合、aかbのどちらかはxの平方根以下で、
どちらかは平方根以上になります。

「両方ともxの平方根未満」ということはあり得ません。
だって、そうしたら、掛けてもxにはなりませんので。
(同様に、「両方ともxの平方根より大きい」ということもありません。)

だから、2から始めて、数の平方根まで調べて約数がなければ、素数としていいのです。
(細かいことですが、上の議論で「以上」「以下」「未満」「より大きい」には注意してください)

問題の場合、最大の数が100未満です。
だから、平方根は、最大でも10未満です。
だからこの場合、本当は10以下の素数(最大の素数は7)に
ついて調べればいいのですが、
念のため11まで調べたのでしょう。

お礼

分かりました！回答してくださり、どうもありがとうございました。

回答No.1

rmz1002

分かりやすく、「26の場合」を考えてみましょうか。
26は確かに「11では割り切れないが、13では割り切れる」数です。
が、13で割った時の商は2ですので、「2の倍数を消すときにすでに消されています」。
他の13で割り切れる数も同様です。（17、19でも）

したがって、「既に消されているので考える必要がない」ということです。

「11より大きい場合～」というのはこの逆で「まだ消されていないけども13や17、19をした時に消されてしまう（=素数ではなくなる）かもしれない」という理由からです。

補足

rmz1002さん、早速のご回答どうもありがとうございます。
「26の場合」の話までは理解出来たのですが、「11より大きい場合～」の話は、やっぱり「商が11より大きい場合」、ということで話されてるのでしょうか…。だとしたら本当にごめんなさい、そこがまだ、よく分からないです…（バカですみません…）。