ここから本文です

次の問題の解き方を教えて下さい 自然数nが,√n(ルートnです)以下のすべての...

kusogami_ns_4さん

2010/8/122:26:53

次の問題の解き方を教えて下さい

自然数nが,√n(ルートnです)以下のすべての素数で割り切れなければ,nは素数であることを照明せよ。

です。

それと,自分にはさっぱりなのですがこの問題はどれくらいの難しさなのでしょうか?

閲覧数:
2,424
回答数:
2

違反報告

ベストアンサーに選ばれた回答

musical_0xdさん

2010/8/123:01:06

約数をさがす作業、やったことありますか?
例えば、
60の約数は何個あるか、といわれたとき、
1, 2, 3, 4, 5, 6,
60, 30, 20, 15, 12, 10
という風に書きますよね。これは、
上に1から順に自然数を書いていく。
下に、それで割り切れたなら商を書く。
続けていって、前に一度書いた数字が出てきたら終了。
という手順で行う作業です。
わかったかと思いますが、√n以上の数で割って割り切れるとしても、その商は、√n以下で、そこまでで挙げてきた数の中にあるから、数える必要がないんですね。
全く同じことです。単に、「約数」という条件で探していたのを「素数」という条件にするだけです。上で書いたようにやっていくなかで、割る数が4とかのときは含めないようにしていくだけです。
あとは、こういうようなことを難しく=厳密っぽく書くだけですね。

直感的な証明だと上のようなものになります。

もう少し厳密に書くなら、例えば、
対偶法が使えそうですね。
なぜなら、「素数である」ことは表しにくいですが、「素数でない=合成数である」ことは比較的表しやすいからです。
というわけで、対偶を証明しましょう。ある命題の真偽とそれの対偶の真偽は一致しますから。
証明したい命題の対偶は、
nが素数でないならば、nは√n以下の素数のいずれかで割り切れる。
というものになります。

まず、
nが素数でない
ということは、nは合成数なので、少なくとも1つの素数pによって割り切ることができることになります。nをpで割った商をqとおくと、
n=pq
と表せますね。
ここで、
qが素数のとき、
仮にp≦√nとすると、その場合はnが√n以下の素数pで割り切ることができていることになるので、題意成立します。
仮にp>√nとすると、この上にさらにqもq>√nであったなら、pq>nになってしまうので、pq=nでなくなってしまいます。そのため、q≦√nでなくてはなりません。ということは、上のと同じように、今度は√n以下の素数qで割り切れることがいえるので、題意成立です。
以上から、qが素数のときは、必ず題意成立です。

qが素数でないとき、
qはまた合成数なので、それを割り切ることのできる素数mが存在するはずで、q=mlとおくと、
n=pq=pml
と書けます。
ここで、また、pについて、p≦√nならば題意成立です。
問題はp>√nのときですが、この場合、qが、即ちmlが、√n以下ということになりますね。
mもlも整数で、qの約数であるので、mもlもqより小さくなります。
つまり、
m<q
かつ、
q≦√n
なので、
m<√n
であることがいえます。
この場合、mは√n以下の素数であり、かつ、nの約数になっているので、nは√n以下の素数で割り切れることになります。
以上から、qが素数でない場合も、かならず割り切れます。

長くなってしまいましたが、まとめると、
nが素数でないならば、nは√n以下の素数のいずれかで割り切れる。
ことが証明できたわけです。全パターン潰しましたから。
ということはこれの対偶も真となり、
自然数nが,√n(ルートnです)以下のすべての素数で割り切れなければ,nは素数であること
が証明できたわけです。

ベストアンサー以外の回答

1〜1件/1件中

fermiumbay2さん

2010/8/122:49:26

どうなのでしょう……厳密な証明は知りませんが、
素数でなければその数は2つ以上の素数の積になっていますよね。
ということは、少なくともその中の一つは、√n以下になります。
√n以上の数ばかりになることは有り得ません。
なので、√n以下に素数がなければ、2つ以上の素数の積にはなれないのです。

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問や知恵ノートは選択されたID/ニックネームのMy知恵袋で確認できます。