素因数分解の可能性の証明

Question

下記の証明をより分かりやすく説明頂けますと有難いです。

背理法で証明する。素因数分解不可能な正の整数が存在すると仮定する。その最小のものを n とする。
素数（および 1 ）はもちろん素因数分解可能なので n は素数ではない。
よって，n は 1 より大きく n より小さい約数を持つ。よって n=ab ( a,b は 1 より大きく n より小さい正の整数）と表せる。

最小性の仮定より a と b は素数の積で表せる。よって n も素数の積で表せるので矛盾。
以上宜しくお願いします。

注）何と何が矛盾するのか、分かりやすく説明頂けますと有難いです。

funoe · Accepted Answer

簡便のための例示の細かいとこにツッコム人ですねぇ。

---
あるクラスの「男子」で一番背の低い生徒が太郎くんだったら、
太郎くんより背の低いクラスメイト[がいたとしたらそれ］は「女子」だというのは理解できますか？
--

太郎君より小さいクラスメイトがいたならば
そのクラスメイトが女子だということは理解できるんですね。

では、正の整数のすべてに赤か青の色が塗られていて
一番小さい青が１００だったら、１００より小さい９９個の整数（１~９９）が赤だってことも理解できるんじゃないですか？

素因数分解できない正の整数の中で一番小さいのがｎだったら、
ｎより小さい正の整数は素因数分解できるのも理解できるんじゃないですか？

tknakamuri · Answer

>下記の場合は、どうなるのでしょうか？
>n=1*10^20なる整数の場合

n = 2^20×5^20 だから仮定に反してます。
これに関して考えても無意味です。

実際は無いものを有ったら矛盾が導かれる
という戦略で証明するのですから
具体的な n で考えることはできません。

funoe · Answer

「赤」は「青」より小さい番号と言う設定（宣言）は何処で行われているのでしょうか？

「青の中の一番小さいやつが１００だったら」の部分ですね。
１０１や１０２やそれ以上の数の色が何色かはわかりませんが、
青の一番小さいのが１００なら、１~９９は赤です。

もし９９が青なら、９９が一番小さい青であって一番小さい青は１００ではありません。
もし９８が青なら、９８が一番小さい青であって一番小さい青は１００ではありません。
もし９７が青なら、９７が一番小さい青であって一番小さい青は１００ではありません。

---
あるクラスの「男子」で一番背の低い生徒が太郎くんだったら、
太郎くんより背の低いクラスメイトは「女子」だというのは理解できますか？

funoe · Answer

あなたは、
-
すべての自然数に「赤」と「青」のどちらかの色が塗られているとして、
青の中の一番小さいやつが１００だったら、１~９９は「赤」だよね。
---
を理解できますか？

funoe · Answer

無数にある、「正の整数」。
そん中には、
「素数の積で表すことのできる整数」と「できない整数」が混じっているかもしれない。
つまり、
できる整数もたくさんあるかもしれないし、
できない整数もたくさんあるかもしれない。

いま、たくさんあるかもしれない「できない整数」の中で一番小さいヤツをｎをしてみよう（背理法の仮定）。
できない整数の中でｎは一番小さいんだから、１から（ｎ－１）までの整数はできるヤツ。

-
すべての自然数に「赤」と「青」のどちらかの色が塗られているとして、
青の中の一番小さいやつが１００だったら、１~９９は「赤」だよね。
---

----------------------------
あるいは、そもそも、
背理法の論理構成がわかっていないのか？

ある仮定をおく。
その仮定をもとに議論していくと、矛盾が生じる。
となると、その仮定が間違っているというほかない。
というのが、背理法の論理構成。

今回のは、「すべての整数はできる整数である」ということを示したいので、
「できないヤツがあるとする」と仮定した。
で、出来ないヤツが１個以上あるなら、その中の一番小さいヤツもあるだろ。
その一番小さいヤツをｎと呼ぶ。
で、イロイロ考えてくと、変なことになった（矛盾した）
ということは「できないヤツがある」という仮定が間違っていたということ。
「できないヤツがある」が間違っているんなら「できないヤツはない」。

----
自然数ａとｂを足したら１０になった。ａかｂのどちらかは５以上である。
なんてのを背理法で示すなら、
「ａもｂも４以下と仮定する」・・背理法の仮定
「ａとｂを足しても８以下にしかならない」・・・★
「足して１０になるという前提に矛盾」
「だから仮定が間違っている」
「つまり、ａかｂは５以上である」
といった感じになるけど、
★の部分、２つの自然数ａとｂを足して８以下になるなんて証明済みの定理があるわけなくて、
「背理法の仮定のもとで」、この命題★は正しい。

元の問題でも、「できないヤツがある」という背理法の仮定のもとで、
・それなら一番小さいやつがある。
・その一番小さいヤツよりさらに小さいヤツはできるヤツである。
・だから・・・、
　という、構成になっている。

funoe · Answer

ｎは、素数の積として表すことのできない数の中で一番小さいヤツ。
（大事なのは「一番小さいヤツ」という点）

ということは、
ｎより小さい正の整数（ｎ－１以下の整数）は、素数の積として表すことができる。

ａはｎより小さい整数だから素数の積として表すことができる。

funoe · Answer

多分、『すべての正の整数は、素因数分解が可能（素数の積としてあらわすこと）』とかいうことを証明しないさいとかなんとか言われている、ってことなのかな？
細かくは、「１」についても問われているのかどうかが気になる（１は素数の積では表せられない。１を素因数分解可能というかというと疑問）のでとりあえずそれには触れないことにする。

すべての正の整数が「＊＊できる」って言ってんだから、「もし、＊＊できない正の整数があるとしたら」ってのが背理法のスタート。
というわけで「素因数分解できない正の整数があるとして、その中の一番小さいヤツをｎとしたら」と書いてある。

で、ｎがどんな数かを細かく検討して、「そんなｎなんて存在しないじゃん」という結論を導き出したい。

まず、ｎは１じゃぁないよね、と書いてある。
（上述した、触れないことにするとした点が大いに気になるが）
で、次にｎは素数じゃないよね、と書いてある。
なんでかっていうと、ｎが素数なら１つの素数の積（？）としてあらわせるから。
で、最後にｎが素数じゃないとしたらどうかを考えている。
素数じゃないってことは、１以外の約数があるってのが「素数じゃない」ことの定義なので、ｎ＝ａｂ　（ａもｂも１ではない）と書ける。
ａやｂは、ｎよりも小さい数だよね。
素数の積で表せないヤツの一番小さいのがｎとしたので、ｎより小さいａやｂは、素数の積で表せることになっちゃう。
aを素数の積　a＝ｉ*ｊ*ｋ
ｂも素数の積　ｂ＝ｌ＊ｍ＊ｎ　とすれば、
ｎは、　ｎ＝ａｂ＝ｉ*ｊ*ｋ*ｌ*ｍ*ｎ　と書けちゃう。
ｎは素数の積で書けない数としたはずなのに、素数の積で掛けちゃったから、こいつは矛盾だよね。

この矛盾のそもそもの原因は、「素因数分解できない正の整数があるとして」が原因だから、結論として「そんな数はない」→「すべての正の整数は素数の積で表すことができる」（まぁ、ホントは２以上の整数だけど）

kairou · Answer

＞証明の中に命題と言う言葉が在りませんでした

「命題」と云う言葉が無くても、何を証明するかが 書いてあった筈です。

＞素数（および 1 ）はもちろん素因数分解可能なので、・・・

これが 変です。
「素数とは 1 と その数自体しか 約数を持たない」ので、
当然 素因数分解は出来ません。
あなたは「素因数分解不可能な正の整数を n 」としたのですから、
a=1, b=n 又はその逆 以外では、 n=ab には出来ません。

ありものがたり · Answer

それでいいんですよ。
末尾に
「よって背理法により、素因数分解不可能な正の整数は存在しない。」
と付記すれば完璧です。
質問は何ですか？

ShowMeHow · Answer

仮定：素因数分解不可能な正の整数が存在する（その最小のものを n とする）
と
n も素数の積で表せる

が矛盾しているので、仮定の「存在する」が誤りと思われます。
命題がなんであるか書いていただくと、もう少し詳しい説明ができるかもしれません。

素因数分解の可能性の証明

簡便のための例示の細かいとこにツッコム人ですねぇ。

>下記の場合は、どうなるのでしょうか？

「赤」は「青」より小さい番号と言う設定（宣言）は何処で行われているのでしょうか？

あなたは、

無数にある、「正の整数」。

ｎは、素数の積として表すことのできない数の中で一番小さいヤツ。

多分、『すべての正の整数は、素因数分解が可能（素数の積としてあらわすこと）』とかいうことを証明しないさいとかなんとか言われている、ってことなのかな？

＞証明の中に命題と言う言葉が在りませんでした

それでいいんですよ。

仮定：素因数分解不可能な正の整数が存在する（その最小のものを n とする）

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング