素数の判定

質問

自然数Nが√Nを越えない最大の整数以下のすべての素数で割り切れなければ、Nは素数である。
この定理の証明について、わからないことがあるので質問します。本の証明では√Nを越えない最大の整数をnとし、Nがnより大きい素数qで割り切れたとすると、そのときの商をpとして、N=pqである。ここで1<p≦n＜q<Nに注意すると、
pが素数ならNは素数pで割り切れるはずだし、pが合成数ならNはpの素因数で割り切れていたはずであり、いずれにしても不合理である。証明終わり。
自分は不合理を示す証明は、背理法を使っていると思ったのですが、その場合自然数Nが素数でないと仮定して証明を始めると思いました。しかし√Nを越えない最大の整数をnとし、Nがnより大きい素数qで割り切れたとすると、という仮定で始まっています。また√Nを越えない最大の整数をnとし、Nがnより大きい素数q以外では割り切れないとすると、という文章の解釈でよいのかと思いましたが、はたして正しい証明なのか疑問が残りました。最後に対偶をとってそれを背理法で証明しているのかと思いました、対偶は、Nが素数でないならば、√Nを越えない最大の整数をnとし、Nはn以下の素数いずれかで割り切れる。ですが、これを背理法で証明しようとすると、
Nはn以下の素数いずれかで割り切れない、という仮定から始まるとおもいました。本の証明の書き出しと違いました。自分で考えた方針では、本の証明とだいぶ違います。
だれか本に書かれた証明で、pで割り切れると何が不合理なのかと、自分の証明の方針のまちがいを指摘してください、お願いします。

回答No.1

tmpname · ベストアンサー

その本は随分分かり難い記述をしているな... 私が採点をするなら×をつけてやりたい。
適当に言葉を補うと：

nを√Nを超えない最大の整数とする。
結論を否定してNが素数でないとする（N=1の時はちょっと考えない）と、NはNより小さい何らかの素数で除することが出来るはずである。しかし、仮定によりn以下の全ての素数で除する事ができないと言っているので、nよりも大きい何らかの素数qで割り切れるはずである。
そこでNをqで割った時の商をpとすると、N=pq。q<Nだからp>1 であって、q≧n+1>√Nであるゆえp<√N、即ちp≦nであって、1<p≦n<q<N。
ここでpが素数であればNはn以下の素数pで割り切れるから仮定に反する。また、pが素数でないとすれば、pの素因子の一つをrとすれば、Nはrで割り切れ、かつr<p≦nであるゆえ、結局Nはn以下の素数rで割り切れるから矛盾である。従って、いずれにしても不合理である。

本の証明は、この位言葉を補わないと理解しづらい。
従って、

> その場合自然数Nが素数でないと仮定して証明を始めると思いました。
その通りです。

> Nがnより大きい素数qで割り切れたとすると、という仮定で始まっています。
これは、「とすると」とは書いてありますが、結局「（Nが素数でないから）nより大きい素数で割り切れるはずだからその一つをqと『おくと』」という意味で、すごく分りづらい。

> ですが、これを背理法で証明しようとすると、
> Nはn以下の素数いずれかで割り切れない、という仮定から始まるとおもいました。本の証明の書き出しと違いました。
上で本の言葉を補いましたが、要は本はその仮定を使っている事をexplicitに書いてくれていないだけです。わかりづらい。

お礼

証明の言葉を補ってくださり、ありがとうございます。

回答No.3

f272

命題: pならばq
p: 自然数Nはn以下のすべての素数で割り切れない
r: 自然数Nはnを超えるすべての素数で割り切れない
q: Nは素数である
ここではp→r→qと証明していきます。

> pにあたる「自然数Nがn以下のすべての素数で割り切れない」を否定すると、「Nがnより大きい素数qで割り切れた」となり

そんな風にはなりません。
pを否定すれば「Nがn以下のある素数で割り切れた」となります。
ここではrを否定して「Nがnより大きい素数qで割り切れた」としています。
これが不合理なのでp→rが証明できたのです。r→qの部分は明らかなので書いていないだけ。

> その場合も不合理が生じれば、背理法ができたということでしょうか？

そんなわけがない。

お礼

p→r→qと3つの命題を使うとは思いませんでした。解説ありがとうございます。

回答No.2

f272

(命題)
「自然数Nがn以下のすべての素数で割り切れない」ならば「Nは素数である」。
(証明)
「Nがnより大きい素数qで割り切れた」と仮定すれば，そのときの商をpとして，(途中略)Nはn以下の素数で割り切れる。これは命題の仮定に反するので「Nはnより大きい素数qで割り切れない」。これと命題の仮定を合わせると「Nは素数で割り切れない」となってNは素数であることが導ける。

> 自分は不合理を示す証明は、背理法を使っていると思ったのですが、その場合自然数Nが素数でないと仮定して証明を始めると思いました。

背理法を使っていると思ったのはよいが，なぜ自然数Nが素数でないと仮定しなければならないのか？ここでは「Nがnより大きい素数qで割り切れた」と仮定すれば不合理だから「Nはnより大きい素数qで割り切れない」としているだけですよ。

> また√Nを越えない最大の整数をnとし、Nがnより大きい素数q以外では割り切れないとすると、という文章の解釈でよいのか

これが「Nがnより大きい素数qで割り切れたとすると」の解釈ということですか？そんなことは書いていませんね。

> 最後に対偶をとってそれを背理法で証明しているのかと思いました

どこにも対偶らしきところはないですね。

> 本に書かれた証明で、pで割り切れると何が不合理なのか

証明しようとしている命題の仮定は「自然数Nがn以下のすべての素数で割り切れない」です。これと明らかに矛盾しているでしょ。

> 自分の証明の方針のまちがいを指摘してください

正しい命題なのですから「対偶をとってそれを背理法」でやっても証明できます。本と同じである必然性はない。

お礼

質問に答えていただき、ありがとうございます。

補足

良ければお返事ください。
命題「pならばq」の否定は、「pであってqでないものがある。」これが成り立つすると不合理がある。というのが背理法と思っていました。今回の定理ではqは「素数である」と考えていて「素数でない」と仮定すると思ったのですが、pにあたる「自然数Nがn以下のすべての素数で割り切れない」を否定すると、「Nがnより大きい素数qで割り切れた」となりその場合も不合理が生じれば、背理法ができたということでしょうか？
命題(定理)の仮定pにあたるものを否定してみても、背理法になるか確認したいです。お返事おねがいします。