ユークリッドの素数無限の証明とは？
- ユークリッドの素数無限の証明は、素数が無数に存在することを証明する数学の定理です。
- 証明の方法は、ある素数のリストを任意に与えたとき、その最小公倍数に1を加えた数が素数または合成数であることを示すことです。
- その証明において、「リスト中の素数は最小公倍数を割り切る」という性質から、「最小公倍数に1を加えた数はリストに含まれない新たな素数である」と結論されます。
- ベストアンサー
ユークリッドの素数無限の証明を教えて
ユークリッドの素数無限の証明で分からないところがあります。 とりあえずWikipwdiaから引用します。 素数が無数に存在することの証明 - Wikipedia https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E3%81%8C%E7%84%A1%E6%95%B0%E3%81%AB%E5%AD%98%E5%9C%A8%E3%81%99%E3%82%8B%E3%81%93%E3%81%A8%E3%81%AE%E8%A8%BC%E6%98%8E a, b, …, k を任意に与えられた素数のリストとする。その最小公倍数 P := a × b × ⋯ × k に 1 を加えた数 P + 1 は、素数であるか、合成数かのいずれかである。素数であれば、最初のリストに含まれない素数が得られたことになる。 素数でなければ、何らかの素数 p で割り切れるが、p はやはり最初のリストに含まれない。なぜならば、リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能だからである。任意の素数のリストから、リストに含まれない新たな素数が得られるので、素数は無数に存在する。 ---- 引用ここまで ---- 前半はわかります。後半の「リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能」の部分がどうもわかりません。 「リスト中の素数は P を割り切る」のは当然ですが、だとするとなぜ「P + 1 を割り切ることは不可能」になるのかつながりませんでした。 なぜ「P + 1 を割り切ることは不可能」なのでしょうか？ この点について教えてください。 よろしくお願いします。
- pringlez
- お礼率99% (2344/2366)
- 数学・算数
- 回答数2
- ありがとう数3
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
リスト中の任意の素数pでP+1を割ろうとするとき，Pはpで割り切れるのだから，P+1をpで割った余りは必ず1になるということです。
その他の回答 (1)
- mitoneko
- ベストアンサー率58% (469/798)
具体的に、考えてみましょう。例えば、5という数字を考えます。これに任意の自然数nをかけて1を足します。 5*n+1ですね。さて、これを5で割った余りはいくつでしょうか?答えは、1です。5を任意の自然数にしても成立します。 理由は、a=nq+r (r<n) を満たすqをaをnで割った時の商といいrを余りというというのが定義ですから。この式で、nとqを入れ替えれば、同じ形になりますよね。 さて、すべての素数のリストなるものを作って、その素数全部の最小公倍数+1を作ったわけです。その素数の中から、任意の素数aを持ってくるとしましょう。すると、作った数は、a*(a以外のリスト内の数の積)+1ですよね。これをaで割った余りは、1。つまり、aでは割り切れないということです。どの数を持ってきても同じ話になりますから、結論として、リスト内のすべての素数で割り切れない数字ということになります。
お礼
解ってしまえば簡単なことですね。でも、具体的な値を示していないのに、存在することの証明になるって、まだ不思議です。 ありがとうございました
関連するQ&A
- 素数が無限個存在すること（エルデシュによる証明）
素数が無限個存在することの証明について、 素数―wikipedia―によれば、エルデシュによる素数の逆数和の 発散性の証明は、素数が無限個存在することの証明にもなっているらしいです。 （証明において、素数が無限個存在することを用いていないため・・・？） http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0 その証明は、 背理法による。 n 番目の素数を pn とする。 素数の逆数和が収束すると仮定すると、 任意の ε > 0 に対してある自然数 N が存在して、 1/pN+1 + 1/pN+2 + 1/pN+3 + ... < ε となる。 ★ いま、 ε = 1/2 としよう。任意の自然数 n に対して ・・・・・・・・ と説明されているのですが、 ★マークの部分がよくわかりません。 素数が無限個存在することを使用しているのでは！？ もし有限なら、はるかに小さいεがとれないのではないでしょうか？ どうかご教授ください。
- ベストアンサー
- 数学・算数
- 素数は無限
質問２点。 １． 「素数は無限に存在する」証明をwikipediaで調べると、 背理法で素数が無数にあることを証明した、 素数の積に1を加えた数が素数であることを証明した」などの誤解をする者がいるが、 いずれも正しくない と書かれています。 wikipediaが常に真実とは限りませんが、 Google検索で素数の無限である証明で検索すると、上記の誤解している人による解説ばかりです。 何を（どちらを）信じればよいか分からずに困っています。 ２． wikipediaによる正しい証明によると、、、 素数の個数が有限と仮定し、p1, … pn が素数の全てとする。その積 P = p1 × … × pn に 1 を加えた数 P + 1 は、p1, …, pn のいずれでも割り切れないので、素数でなければならない。しかし、これは p1, …, pn が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無数に存在する。 これは、背理法による証明だと思うのですが、、、、 お手数ですが、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素数は無限に多く存在することの証明（ユークリッドの別証）を二つの添削
ユークリッドの証明は背理法を用いた証明。 素数を有限個とするならその最大素数をpnとして素数を小さい順にp1,p2,…,pnとした時 N=p1*p2*p3*…pn + 1 全ての自然数は素因数に分解できるのでｐ1～pnの少なくとも一つ因数に持つはずだが、どれで割っても1あまる。これはpnが最大の素数であることに矛盾 素数は無限に存在する。 といった証明。今回はこれの別称として以下の漸化式を用いたものを解けという問題です。 ◆a_{n}:=2^(2^n) + 1, n=1,2,3,… を用いた証明 この時任意のm≠nに対しa_{m}, a_{n}は互いに素である。実際n>mの時 a_{n} - 2 = 2^(2^n) - 1 ={2^2^(n-1) + 1}{2^2^(n-1) - 1} =a_{n-1}*(a_{n-1} - 2) =a_{n-1}*a_{n-2}*…*a_{m}*(a_{m} - 2) となるのでa_{m},a_{n}の公約数dは2の約数でなければならない。他方a_{m},a_{n}は奇数であるから（←漸化式より）d=1となる。すると各a_nを素因数分解すると少なくとも一つ素因子pnが得られ、これらはnが異なれば一致しない。かくして無限個の素数p1,p2,p3,…,pn,…が得られた□ ◆正整数の列a_nを次のように定める a_{n+1} = a_{n}*(a_{n} - 1) + 1, a_{1} = 2 これを用いて素数が無限であることを示すのですが 任意のm≠nに対して a_{n} - 1 = a_{n-1}*(a_{n-1} - 1) = a_{n-1}*a_{n-2}*(a_{n-2} - 1) = a_{n-1}*a_{n-2}*…*a_{m}*(a_{m} - 1) よりa_{n},a_{m}の公約数は1の約数でなければならない。よってa_{n},a_{m}は互いに素である。 すると各a_nを素因数分解すると少なくとも一つ素因子pnが得られ、これらはnが異なれば一致しない。かくして無限個の素数p1,p2,p3,…,pn,…が得られた□ これら2つの証明はこれであっているでしょうか？
- ベストアンサー
- 数学・算数
- 素数は無限に存在する
素数が有限であると仮定し、その最大のものをNとする。 ａ、b、cを自然数とした場合、すべてのａについて Ｎ＋ａ＝b＊cとなるｂ、ｃが存在する。 この式を変形すると Ｎ＝ｂ＊ｃ－ａとなる。 ところがａ＝ｂの場合、ａはＮの約数となり最初の仮定と矛盾する。 よって素数は無数にある。 この証明は正しいのですか？というのはこの矛盾をつくことによって、有限ではない！！って感じがしないんですよね。a=bの時はＮは素数ではない！！っていうのは分かるんですけど、a≠bでちょっと特別の場合（a=1,b=4,c=5など）は成立しちゃうんじゃない！？っていうのもあるし（aの値が変化することによってｂ、ｃの値も変化するだろうし・・・）、Ｎは素数ではないっていう証明をしただけで、「最大の」素数ではないって感じがしないんですよね・・・ こっちの証明は普通に納得するんですが・・・ 定理が成立しないとすると，素数は有限個である．それらの素数をP1,P2,P3,・・・,Pnとする．このとき，Q=(P1P2P3…Pn)+1を考えると， QはP1,P2,P3,・・・,Pnのどれでも割り切れない．したがって， Qを素数の積として表したとき，この積に現れる素数はP1,P2,P3,・・・,Pnのいずれとも異なる． これは矛盾である。したがって定理が証明された． なんかすっきりしなて非常に困ってます。誰か教えてください。お願いします。
- ベストアンサー
- 数学・算数
- ユークリッド幾何学において 真偽が証明できない問題として 例えば『無限
ユークリッド幾何学において 真偽が証明できない問題として 例えば『無限遠点で平行線は交わる』は その例と考えますが、合っているでしょうか。なぜなら 無限領域は 定義されていないからです。 ユークリッド幾何学の５公理は有限領域で定義されているとし、その場合に真偽が証明できない問題として 例えば『X・X＝－１は根が存在しない』はその例と考えますが、合っているでしょうか。なぜなら 複素数領域は定義されていないからです。 なお 公理は証明対象にならない 命題と考えます。
- ベストアンサー
- 数学・算数
- 素数 無限
「素数は無限にある」証明について。（たびたびすみません） 素数が有限個で n 個と仮定し 素数を P1, P2, P3, …, Pn とする P = (P1 x P2 x P3 x…x Pn) + 1 とおくと、 PはP1からPnで割り切れない ・・・理解できます。 従って、 Pは n+1 個目の新たな素数 ・・・★ここが理解できません。 Pは、１～P-1の数で割り切れないなら、素数（定義そのもの）ですが。 Pは、P1, P2, P3, …, Pn以外の合成数（素数以外の数）で割り切れる可能性もあると思います。 中学生ぐらいの証明のようですが、自分の頭の悪さに苦しんでいます。 2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509
- 締切済み
- 数学・算数
- メルセンヌ素数でない素数は無限に存在するか？
素数は無限に存在することが知られています。 ユークリッドやオイラーの証明があります。 また、コンピュータでは、大きい素数を探すときに、 メルセンヌ素数を探します。 しかし、メルセンヌ素数は無限にあるかどうかわかりません。 ここで、質問です。 メルセンヌ素数でない素数は、無限にあるのでしょうか？ 素数はメルセンヌ素数かメルセンヌ素数でない素数のどちらかです。 その二種類を合わせると、無限個ありますから、 メルセンヌ素数が有限個ならば、メルセンヌ素数でない素数は無限個あるとわかります。 でも、メルセンヌ素数は有限個しか見つかっていないだけで、 本当に有限個かどうかはわかりません。 メルセンヌ素数でない素数が無限個あるかどうかもわからないのではないでしょうか？ それとも、他の方法で、わかるのでしょうか？ 例えば、メルセンヌ数（素数とは限らない）とメルセンヌ数（素数とは限らない）の間には、 ２個以上のメルセンヌでない素数が存在することがわかっているとか。 でも、ずっと先に行くと、素数はすべてメルセンヌ素数になっているということは 考えられないでしょうか？ しかし、双子素数が無限に存在するならば、メルセンヌ素数でない素数が無限に存在しそうですね。 双子素数より弱くても、よさそうですね。 素数分布とか考えると、どうなるのでしょうね。 やっぱり、メルセンヌ素数でない素数は無限個あるような気がしてきました。
- ベストアンサー
- 数学・算数
- 素数の分類と無限性に関して。
素数の分類と無限性に関して。 ※＾は乗数の意味です。 8n+1型の素数が無限に存在することの証明 原始根の存在（素数 p を法とする整数環 Z/pZ の乗法群が位数 p - 1 の巡回群であること）を使う。 x を整数とする時x＾4 + 1 の奇素数因子を p とする。 x＾4 ≡ - 1 (mod. p) より、両辺を2乗することでx^8≡1となる。 x の p を法とする整数環 Z/pZ の乗法群での位数は 8 で有るから、 p ≡ 1 (mod. 8) となる。ここで、 p ≡ 1 (mod. 8) となる素数が有限個であったとする時、その総乗積を P として、 (2P)＾4 + 1 の奇素数因子を考えると矛盾が出る。 私は2PをX"とおいて上と同様に考えました。 この証明の流れや、8n＋1型の素数が無限に存在することは理解できるのですが、上の証明における「位数は 8 で有るから、 p ≡ 1 (mod. 8) となる」の部分がどのようにして言えるのかが分かりません。フェルマーの小定理を用いているのでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法の証明
ユークリッドの互除法なんですが、これを使った証明がわからないので質問させてください。 a,bは正の整数で、b≦aである。 r_0=a、r_1=bとしq_iとr_iは整数で0<r_i<r_(i-1)である。(qについては特に指示はありません) このとき r_0=r_1*q_1+r_2 r_1=r_2*q_2+r_3 ・ ・ ・と続き r_(n-2)=r_(n-1)*q_(n-1)+r_n r_(n-1)=r_n*q_n が成り立つ。 n≧2の時、ユークリッドの互除法はgcd(a,b)=ax+byとなる整数(x,y)を持つことを証明しなさい。 これは帰納法を使えばいいのでしょうか？ n=2の時にr_2=r_0-r_1*q_1が成り立つことはr_(n-1)=r_n*q_n にn=2を代入して示せるのですがn=k、n=k+1の時にどうすればうまく証明できるのかわかりません。 どなたか教えて下さい。
- ベストアンサー
- 数学・算数
お礼
あー、意外と簡単なことでしたね。 「割り切ることは不可能」ではなく「余りは必ず1になる」と書いてくれれば分かったのに、と思いますが、その程度はわからなくちゃいけないってことですね。 精進します。ありがとうございました