• 締切済み
  • 困ってます

4n+1型の素数について

4n+1型素数の無限性を示せ。 次のように考えた。行き詰まったのでアドバイスをお願いします。 4n+1の素数は有限で最大をpとする。 k=4(5×13×・・×p)+1 とおく。 kは合成数のとき、kは4n+3型の素数の偶数個の積に素因数分解できるから、  k=(4x+1)(4y+1) x,y自然数   =16xy+4x+4y+1  となる。  このあとの矛盾の導き方が見えないので、この流れの証明とすると このあとどうなるのか、よろしくお願いします。

共感・応援の気持ちを伝えよう!

  • 回答数2
  • 閲覧数1052
  • ありがとう数1

みんなの回答

  • 回答No.2
  • R_Earl
  • ベストアンサー率55% (473/849)

ANo.1です。 > 平方剰余の相互法則の第1補充法則を使うために、2乗しておくのでしょうか。 そうですね。 > もし、平方剰余の相互法則の第1補充法則を使わないとするとどのような解答になっていくのか。 >  ア k=4(5×13×・・×p)+1とおいてできるのか。 >  イ k = 4(5^2 × 13^2 × … × p^2) + 1 とおいて、平方剰余の   相互法則の第1補充法則を使わないとするとどうなるのか。 申し訳ないのですが、この2点に関しては分かりません。

共感・感謝の気持ちを伝えよう!

  • 回答No.1
  • R_Earl
  • ベストアンサー率55% (473/849)

前回3n + 1型素数の質問に回答した者ですが、 私の回答は誤りでした。申し訳ありません。 4n + 1型素数に関しては、合同式(と平方剰余)を利用した証明方法があります。 >  このあとの矛盾の導き方が見えないので、この流れの証明とすると > このあとどうなるのか、よろしくお願いします。 k = 4(5 × 13 × … × p) + 1と置くのではなく、 k = 4(5^2 × 13^2 × … × p^2) + 1と置きます。 kの素因数の一つをqと置くと 4(5^2 × 13^2 × … × p^2) + 1 = q × r (rは整数) と置けます。 kは5 ~ pの4n + 1型素数では割り切れないので、 qは5 ~ pの4n + 1型素数に含まれない素数となります。 よってqが4n + 1型素数であることを示せば、 「qは5 ~ pの中にはない新たな4n + 1型素数である」と 証明したことになります。 4(5^2 × 13^2 × … × p^2) + 1 = q × rより、 4(5^2 × 13^2 × … × p^2) + 1 ≡ 0 (mod q)が常に成り立ちます。 さらに変形して 4(5^2 × 13^2 × … × p^2) ≡ -1 (mod q) ∴(2 × 5 × 13 × … × p)^2 ≡ -1 (mod q) 平方剰余の相互法則の第1補充法則より、 (2 × 5 × 13 × … × p)^2 ≡ -1 (mod q)が常に成り立つのであれば qは4n + 1の形となることが言えます。 よってqは、5 ~ pの中にない新たな4n + 1型素数であるということになります。

共感・感謝の気持ちを伝えよう!

質問者からの補足

平方剰余の相互法則の第1補充法則を使うために、2乗しておくのでしょうか。 もし、平方剰余の相互法則の第1補充法則を使わないとするとどのような解答になっていくのか。  ア k=4(5×13×・・×p)+1とおいてできるのか。  イ k = 4(5^2 × 13^2 × … × p^2) + 1 とおいて、平方剰余の   相互法則の第1補充法則を使わないとするとどうなるのか。 愚問とは思うか゛、よろしくお願いします。  

関連するQ&A

  • 3n+1 の素数について

    3n+1 型 の素数の無限性を証明せよ。 次のような証明をしようとしたが、うまくいきません。アドバイスをお願いします。  3n+1型の素数は有限とし、最大な素数をpとする。  k=3(7×13×・・・×p)+1 とおく。  kは合成数であるから、素因数分解され、3n+2型の偶数個の積になる。(3n+1型の最大素数がpであることから)    *このあとの証明がうまくいきません。よろしくお願いします。

  • 双子素数予想の類似、算術級数定理の類似

    素数を小さい順にp(1),p(2),,,とします。 {p(m)-p(n)|m>n}、 {p(m)+p(n)|m≦n}、 {p(m)+p(n)|m<n}、 {p(n+1)-p(n)|nは自然数}、 {p(n+1)+p(n)|nは自然数}、 などを考えます。 目的は、素数に関する様々な定理や予想をそれらで言い換えたいのです。 双子素数は無限個ある(双子素数予想) ⇔{p(n+1)-p(n)|nは自然数}において、p(n+1)-p(n)=2となるnは無限個 ♯そうすると疑問に思うのは、 たとえば{p(n+1)-p(n)|nは自然数}のある偶数の元について、それを満たすnが有限個のものは存在するのでしょうか? 初項aと公差dが互いに素であるような等差数列のなかに素数が無限に存在する(算術級数定理) ⇒{p(m)-p(n)|m>n}において、p(m)-p(n)="dの倍数"となる(m,n)は無限個 ♯そうすると疑問に思うのは、 たとえば{p(m)+p(n)|m>n}において、p(m)+p(n)="dの倍数"となる(m,n)は無限個でしょうか? ♯これはd=2であれば明らかに正しそうです。 d=3とかのときはどうなのでしょう? ♯さらに、2つの合成数の差の集合、または、和の集合とかを考えたときに、成り立つ定理、予想される事実はあるのでしょうか? ♯こういった言いかえができる定理とかは他にありますでしょうか?

  • すばやく素因数分解する方法は?

    「暗号解読」(サイモン・シン(著)青木薫(訳) 新潮社)という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数(合成数)を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法(素因数分解)を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法(アルゴリズム)を知りたいです。

  • 素数は無限に多く存在することの証明(ユークリッドの別証)を二つの添削

    ユークリッドの証明は背理法を用いた証明。 素数を有限個とするならその最大素数をpnとして素数を小さい順にp1,p2,…,pnとした時 N=p1*p2*p3*…pn + 1 全ての自然数は素因数に分解できるのでp1~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つの証明はこれであっているでしょうか?

  • 素数の素因数分解

    素数(例えば17)の素因数分解について  (1)すでに素因数分解は終わっている (17の素因数分解は17)  (2)素因数分解はできない のどちらの見解が正しいですか?

  • 素数の分類に関して

    前回質問させていただいた証明に関することなのですが、最後の一文が分からないためもう一度質問させていただきます。 [類題] 「8n + 3 型の素数は無限に多くある事を示せ。」の略解。 *)文中のp^は複素数pの共役な複素数です。例えば、p=1+iの場合、p^は1-iのことです。 また、a2 はaの二乗という意味です。  証明)もし 8n + 3 型の素数が有限個であったとし、その全体を p1, p2, ... , pn とする。 P = p1p2 ... pn + √2 i と置いて、これを単項イデアル整域 Z[√2 i ] で素元分解する。 N (P) = PP^ は奇数であるから(正確には、 N (P) ≡ 3 ( mod. 8 ) 、) P の有理整数の素因数は奇数である。この因子は PP^ の中では偶数冪で出てくるから、その部分は 8n + 1 型である。又、 P は有理整数に同伴でないから、a + b √2 i 型 (b ≠ 0, 有理整数の素因子と同伴でない物) の因子がある。PP^ は奇数であるから a は奇数である。更に、この a + b √2 i 型の因子の b が偶数であるとすると、 N( a + b √2 i ) = a2 + 2b2 ≡ 1 (mod. 8) であるから、 この形の b が全て偶数であるとすると PP^ ≡ 3 (mod. 8) と矛盾する。従って b が奇数の物 a + b √2 i が有るが、素元分解の一意性により、N( a + b √2 i ) = a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8) となり有限性に矛盾。故にこの型の素数は無限個。 素元分解の一意性により、N( a + b √2 i ) = a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8) となり有限性に矛盾。 における a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8)となった場合なぜ有限性に矛盾していると言えるのでしょうか。 a2+2b2が素数でないならば矛盾はしてないのでしょうか。 よろしくお願いします。

  • 素数 無限

    「素数は無限にある」証明について。(たびたびすみません) 素数が有限個で n 個と仮定し 素数を P1, P2, P3, …, Pn とする P = (P1 x P2 x P3 x…x Pn) + 1 とおくと、 PはP1からPnで割り切れない ・・・理解できます。 従って、 Pは n+1 個目の新たな素数  ・・・★ここが理解できません。 Pは、1~P-1の数で割り切れないなら、素数(定義そのもの)ですが。 Pは、P1, P2, P3, …, Pn以外の合成数(素数以外の数)で割り切れる可能性もあると思います。 中学生ぐらいの証明のようですが、自分の頭の悪さに苦しんでいます。 2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509

  • 二乗の形は素因数分解すると同じ素数を2個一組になるようにもっているはず!!

    他のサイトである質問をしたら、 こういう回答がきました。 36=6^2や64=8^2というある自然数の2乗になる数は、 同じ自然数を2個かけてできているので、 素因数分解すると同じ素数を2個1組になるように持っているはずです。 この文章の、 おんなじ自然数を2個かけてできているので、 素因数分解すると同じ素数を2個1組になるように持っているはず という意味がわかりません。 なぜ持っているはずなのでしょうか? 詳しく教えてください。 一応、他のサイトで質問したものをのせておきます。 http://detail.chiebukuro.yahoo.co.jp/qa/question_detail.php?qid=1125966436

  • 双子素数についてのことです

    双子素数がむげんにあるということの証明は これで充分じゃないでしょうか? nは2以上の自然数 (1~n 番目の素数をかけていった積)+1 は素数 (1~n 番目の素数をかけていった積)-1 は素数 (1~n 番目の素数をかけていった積)±1 は双子素数 素数は無限個あるので双子素数も無限個あることになる これでいいのではないでしょうか?

  • 素数を自動的に作る

    2から順番に無限に素数を作り続けるソフトはどこかにありますか。 実はゴールドバッハの予想 「すべての偶数は二つの素数の和で表される。」 が非常に気になりまして今日まで400ぐらいまでは実証したのですがこれが1万を超えるととても私のキャパでは対応できません。  せめて数字を入れたら素因数分解をしてくれるソフトなんてありませんか?