素数

質問

素数でない数は、素数で割り切れる。証明は可能でしょうか？

ユークリッドの定理で悩んでいます。

素数でない数は、素数でない数でしか割り切れない場合もあるのではないでしょうか？
よろしくお願いします。

回答No.2

sunflower-san · ベストアンサー

素数の定義はご存じですか？
素数でない数が、素数で割り切れるということは定義から明らかですよ。

素数とは1と自身でしか割り切れない数のことですよね。
逆に素数でない数にはそれ以外の約数があるわけです。(ないなら定義により素数ですから)
素数でない数Aが、素数でない数B(1<B<A)で割り切れるなら、Bもまた「素数でないので」、ある自然数C(1<C<B)で割り切れるはずですね。
Cが素数でないなら、さらにD(1<D<C)で割り切れ、、、、

と続きますが、A>B>C>D>・・・>1なのでいずれこの操作は止まります。
その数をXとすると、Xは1<Y<Xであるどんな自然数でも割れないので素数です。
そして、Xは操作から明らかなようにAの約数です。

お礼

ご回答ありがとうございます。

>素数でない数にはそれ以外の約数があるわけです。
ここまでは、すんなり理解できました。
その約数が素数が含まれる証明は、明らか（簡単に）できないのでしょうか？

以下、引用------------

a, b, …, k を任意に与えられた素数のリストとする。その積 P := a × b × … × k に 1 を加えた数 P + 1 は、素数であるか、素数でないかのいずれかである。素数であれば、最初のリストに含まれない素数が得られたことになる。素数でなければ、何らかの素数 p で割り切れるが、p はやはり最初のリストに含まれない。なぜならば、リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能だからである。任意の素数のリストから、リストに含まれない新たな素数が得られるので、素数は無数に存在する。

回答No.7

中村 拓男（@tknakamuri）

仮定から a, b は素因数を持つ。

nは素因数を持たないもっとも小さな数と仮定したからです。

回答No.6

中村 拓男（@tknakamuri）

2以上の整数で素数で割り切れない合成数が存在するなら、下限が２であるから
最小値 n が存在するはずである。

これを n = ab とすると、n>a, n > b であるから、仮定から a, b は素因数を持つ。
すると n は 素数で割り切れてしまう。

これは矛盾であるから n は存在しない。

ユークリッド原論の7巻。

お礼

ご回答ありがとうございます。

>仮定から a, b は素因数を持つ。
この部分を詳しく教えていただけますでしょうか？

回答No.5

sunflower-san

回答No.3は「1以外の」自然数は素数で割り切れる、ということを示した、の誤りです。

訂正します。

回答No.3

sunflower-san

先ほどの回答No.2 では、任意の自然数が素数の約数をもつことの証明をしたのですが、ご理解いただけましたか？

補足で引用されたのはユークリッドによるとされる、素数が無限個存在することの証明ですね。これは非常に簡潔で分かりやすい証明だと思うのですが、納得されていないのはどの部分でしょうか？

お礼

>非常に簡潔で分かりやすい証明

自分が相当頭が悪いみたいです。
理解ができません。

-----------
素数でなければ、何らかの素数 p で割り切れるが、p はやはり最初のリストに含まれない。なぜならば、リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能だからである。
------------
がよく理解できていません。

回答No.1

f272

素因数分解って知っているか？