締切済み

メルセンヌ数

2012/11/04 23:09

定理の証明もともと英語の文です。（教科書が英語） The numbers Mp (p prime) are either pseudoprimes for the base 2 or are prime numbers. That is, Mp │ 2^Mp - 2, for all primes p. 私は Mp=2^p-1 (pは素数) Mpは２を底にした擬素数or素数つまりすべての素数pに対して Mp│2^Mp - 2 である。と訳しました証明がわからなくて困ってます。どなたかわかりやすく証明教えてください（＞＜）

susuken23
お礼率12% (1/8)

数学・算数
回答数2
ありがとう数0

みんなの回答 （2）
専門家の回答

みんなの回答

Tacosan
ベストアンサー率23% (3656/15482)

2012/11/05 23:57 回答No.2

実際に Mp と 2^Mp-2 を書いてみればわかるよ.

Tacosan
ベストアンサー率23% (3656/15482)

2012/11/05 11:01 回答No.1

p|Mp-1 だから.

質問者

補足 2012/11/05 23:35

もう少し詳しくお願いします(>_<)

関連するQ&A

素数

素数でない数は、素数で割り切れる。証明は可能でしょうか？ユークリッドの定理で悩んでいます。素数でない数は、素数でない数でしか割り切れない場合もあるのではないでしょうか？よろしくお願いします。
立法数=立法数×立法数

複素数の範囲で、立法数=立法数×立法数が成り立つ理由を教えて下さい。オイラーがフェルマーの最終定理n=3の証明で用いた定理みたいなのですが…。
素数で困ってます

Pを『素数』とする。と条件にあり、Pを含む方程式や、その他諸々の条件が与えられているタイプの問題で誘導問題の一つが、Pは素数であることの証明を求めていて計算の結果 Pが『複素数』になったのですが『複素数』という数は『素数』にという数の集合の中に含まれるにしていいんですか？漢字的にはよさそうに思えるけど…
素数　再帰関数

メイン #include<stdio.h> extern void count_primes(void); extern void print_primes(void); int max; int count; int primes[1000] int main(void) { printf("Uper limit: "); scanf("%d",&max); count_primes(); print_primes(); } 素数を求める（関数呼び出し） extern int nextprime(int n); extern int max; extern int count; extern int primes[]; void count_primes(void) { int i; count=0; for(i=2;i<=max;i=nextprime(i)){ primes[count++]=i; } リカーバシブ（次の素数） int nextprime[int n] { int i; for(;;){ n++; for(i=2;i*i<=n;i=nextprime(i)){ if(n%i==0) break; } if(i*i>n) break; } return n; } 素数プリント #include<stdio.h> extern int count; extern int primes[]; void print_primes(void) { int i for(i=0;i<count;i++){ if((i>0)&&(i%10==0) printf("\n"); printf(" %6d",primes[i]); } printf("\n素数の数　%d\n",count); } これら４つのモジュールで素数　nが求められますがアルゴリズム理解できません。この２つの関数のアルゴリズムについて、ご教授ください。め
素数　無限

「素数は無限にある」証明について。（たびたびすみません）素数が有限個で 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
素数は無限

質問２点。１．「素数は無限に存在する」証明をwikipediaで調べると、背理法で素数が無数にあることを証明した、素数の積に1を加えた数が素数であることを証明した」などの誤解をする者がいるが、いずれも正しくないと書かれています。 wikipediaが常に真実とは限りませんが、 Google検索で素数の無限である証明で検索すると、上記の誤解している人による解説ばかりです。何を（どちらを）信じればよいか分からずに困っています。２． wikipediaによる正しい証明によると、、、素数の個数が有限と仮定し、p1, … pn が素数の全てとする。その積 P = p1 × … × pn に 1 を加えた数 P + 1 は、p1, …, pn のいずれでも割り切れないので、素数でなければならない。しかし、これは p1, …, pn が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無数に存在する。これは、背理法による証明だと思うのですが、、、、お手数ですが、よろしくお願いします。
素数定理をこのように解釈しても良いか。

素数定理とは、「大きな自然数ｘが素数である確率は１／（log ｘ）」という物ですが、これを元に次の事が言えるでしょうか？１　２と５を除けば素数は一の位が１，３，７，９の　　どれかになり、各グループの素数は無限個ある。２　素数が現れる確率は４つのグループそれぞれで　　等しい。直感的にはどちらも正しいような気がしますがいかがでしょうか？１に関してですが素数が無限個あることの証明は、非常に簡単です。有限個だとしたらそれらの全ての積に１を加えたものも素数になってしまうので素数は、無限個あります。しかし各４つのグループごとにある事を証明しようとするとちょっと手が止まってしまいます。２は、完全にお手上げです。素数定理には、一の位が何であるかで場合分けしていないのでまぁ正しいような気がしますが。。。どなたかご意見お願いします。
素数は無限に存在する

素数が有限であると仮定し、その最大のものを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のいずれとも異なる．これは矛盾である。したがって定理が証明された．なんかすっきりしなて非常に困ってます。誰か教えてください。お願いします。
素数？？

すみません、すごい単純な問題かもしれないんですけど… [問] P が素数とする。 ab が P で割り切れるならば、a は P で割り切れる。または、b は P で割り切れる。この証明を考えているんですが、なんか当たり前というか… 素数 ←ってのが証明で必要だと思うのですが、なかなかしっくりこなくて困っています。どのように解けばいいのでしょうか？？くだらない問題ですみませんが、よろしくお願いします。
素数の分類と無限性に関して。

素数の分類と無限性に関して。 ※＾は乗数の意味です。 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) となる」の部分がどのようにして言えるのかが分かりません。フェルマーの小定理を用いているのでしょうか？よろしくお願いします。
素数　反例

素数が無限であることの証明について。 http://homepage2.nifty.com/mathfin/hairihou/hairihou03.htm 素数が無限個でないことがある。すなわち，素数が有限個であることがあると仮定し、　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（反例の存在を仮定）　その個数をｎ個とする。すべての素数を小さい方から順に　　　　　　　　　P1，P2，P3 ，・・・・・・，Pn　　　　　とおける。ここで，　　　　　　　　　P = P1×P2×P3×・・・・・・×Pn + 1 　　　により，自然数Pをつくると，　　　Pは， P1，P2，P3 ，・・・・・・，Pn のいずれで割っても１余る。　　　　よって，Pは１と自分自身以外に約数を持たないから素数である。　　　これはPnよりも大きい素数が存在することを意味しており，矛盾が生ずる。　　　よって，素数が有限個であることはない（反例は存在しない）　　　ゆえに，素数は無限に存在する --------------------------------------------- P=2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 という反例がありますが、上記の証明は間違いということですか？
【C→JAVA】素数の組の数を求めるプログラム

以下はC言語のプログラムです。標準入力に正の偶数値 n（2≦n≦10,000）を入力すると足して n になる素数の組の数を求め、標準出力に出力するプログラムなのですが、これをJAVA用のプログラムに置き換えるとするとどのようなプログラムになるのでしょうか？よろしくお願いいたします。 #include <stdio.h> #include <math.h> //Compiler version gcc 6.3.0 #define N 10000 int primes[N + 1] = {0}; void sieve(int); int main() { int n,count = 0; sieve(N); scanf("%d",&n); for (int i = 1;i <= n / 2 + 1;i++) { for (int j = i + 1;j < n;j++) { if (primes[i] && primes[j] && i + j == n) { count++; } } } printf("%d\n",count); return 0; } void sieve(int n) { int limit = (int)sqrt(n) + 1; for (int i = 2;i <= n;i++) { primes[i] = 1; } for (int i = 2;i < limit;i++) { if (primes[i]) { for (int j = 2; i * j <= n;j++) { primes[i * j] = 0; } } } }
素数の分類と無限性に関して。以前質問させていただいたことの延長になりま

素数の分類と無限性に関して。以前質問させていただいたことの延長になります。 ※＾は乗数の意味です。 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"とおいて上と同様に考えました。同じ方法を用いることで証明することはできたのですが、この証明の中で用いている「位数は 8 で有るから、 p ≡ 1 (mod. 8) となるの部分に関してラグランジュの定理　　　　　　　位数nの有限郡Gの任意の部分郡Hの位数はGの位数の約数であるを用いた場合、GとHに当たる部分はどこになるのでしょうか。今の段階では、nがｐ－１にあたり、Hの位数が８と考えています。ｐが素数で、８はｐ－１の約数になるとの考えは当っているでしょうか・・？よろしくお願いします。
素数の判定

自然数Nが√Nを越えない最大の整数以下のすべての素数で割り切れなければ、Nは素数である。この定理の証明について、わからないことがあるので質問します。本の証明では√Nを越えない最大の整数をnとし、Nがnより大きい素数qで割り切れたとすると、そのときの商をpとして、N=pqである。ここで1<p≦n＜q<Nに注意すると、 pが素数ならNは素数pで割り切れるはずだし、pが合成数ならNはpの素因数で割り切れていたはずであり、いずれにしても不合理である。証明終わり。自分は不合理を示す証明は、背理法を使っていると思ったのですが、その場合自然数Nが素数でないと仮定して証明を始めると思いました。しかし√Nを越えない最大の整数をnとし、Nがnより大きい素数qで割り切れたとすると、という仮定で始まっています。また√Nを越えない最大の整数をnとし、Nがnより大きい素数q以外では割り切れないとすると、という文章の解釈でよいのかと思いましたが、はたして正しい証明なのか疑問が残りました。最後に対偶をとってそれを背理法で証明しているのかと思いました、対偶は、Nが素数でないならば、√Nを越えない最大の整数をnとし、Nはn以下の素数いずれかで割り切れる。ですが、これを背理法で証明しようとすると、 Nはn以下の素数いずれかで割り切れない、という仮定から始まるとおもいました。本の証明の書き出しと違いました。自分で考えた方針では、本の証明とだいぶ違います。だれか本に書かれた証明で、pで割り切れると何が不合理なのかと、自分の証明の方針のまちがいを指摘してください、お願いします。
4n+1型の素数について

４ｎ＋１型素数の無限性を示せ。次のように考えた。行き詰まったのでアドバイスをお願いします。４ｎ＋１の素数は有限で最大をｐとする。 k=4(5×１３×・・×ｐ)＋１　とおく。ｋは合成数のとき、ｋは４ｎ＋３型の素数の偶数個の積に素因数分解できるから、　ｋ＝（４ｘ＋１）（４ｙ＋１）　ｘ，ｙ自然数　　＝１６ｘｙ＋４ｘ＋４ｙ＋１　　となる。　このあとの矛盾の導き方が見えないので、この流れの証明とするとこのあとどうなるのか、よろしくお願いします。
ユークリッドの素数無限の証明を教えて

ユークリッドの素数無限の証明で分からないところがあります。とりあえず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 を割り切ることは不可能」なのでしょうか？この点について教えてください。よろしくお願いします。
独習C　素数テスタ・・・分からない

忙しい中失礼します。 ”素数”を確認するプログラムについて質問があります。現在独習Cを用いて勉強中なのですが、下記のプログラム理解に苦しんでいます。宜しければアドバイスを下さい。下記のプログラム/*素数テスタ*/内から、質問(1)部：for(; num <=1; )の意味は’１’よりも大きな数字を入れれば、for文のループを抜ける→この考えで合っている、と自分では思っていますが、間違っているのでしょうか?　ご指摘願います。質問(2)部：１．num=5の場合、for ( i=2; i <= num / 2; i = i+1)　→　i <= num / 2はi <= 2となる。→i <= 2となり、for文のループを抜ける。→ if ((num % i) == 0) の条件は成り立たない。→　is_prime = 1のため、"素数です"と表示される。→納得！２．num=9の場合、for ( i=2; i <= num / 2; i = i+1)→　 i <= num / 2は i(=2) <= 4となり、 i = i+1の’i’部が’4’となった後for文のループを抜ける。→if ((num % i) == 0)はnum % iは　9%4で’1’余り、となり、if ((num % i) == 0) の条件は成り立たない。→is_prime == 1 の状態がキープされる。→"素数です"と表示される、と思いきや"素数ではありません"と表示される。で、ここで何故"素数ではありません"と表示されるのかが分かりません。頭の中では’９’が素数ではないのは分かりますが、プログラムの中でどういう経路を辿り、"素数ではありません"と表示されるのでしょうか。その過程の説明を欲しています。宜しければ、アドバイスを下さい。 /*素数テスタ*/ #include <stdio.h> int main(void) { int num = 0, i, is_prime; for(; num <=1; ){ //質問(1) printf("判定したい数を入力して下さい: "); scanf("%d", &num); } /*約数があるかどうかを調べる*/ is_prime = 1; for ( i=2; i <= num / 2; i = i+1) //質問(2) if ((num % i) == 0) //質問(2) is_prime = 0; //質問(2) if (is_prime == 1 ) printf("素数です"); else printf("素数ではありません"); return 0; }
C言語の素数判定について質問です。

C言語の素数判定について質問です。「与えられた数値以下で、最大の素数を返す関数を作成しなさい。素数が存在しない場合、０を返すこと。 int max_prime (int x);を使用する。」という問題なのですが。まったくの初心者なので何をすればよいか分かりません。例として以下のようなプログラムを見せられたのですが、他の例などないでしょうか。もし分かるかたがいらっしゃれば教えていただけないでしょうか。よろしくお願いします。 #include<stdio.h> int is_prime (int i){ int a; for(a=2;a<=i-1;a++){ if(i%a == 0){ return i; } } return 0; } int max_prime(int x){ int i; for(i=x;i>1;i--){ if(is_prime(i)!=i){ return i; } } return 0; } int main(void){ int x,z; scanf("%d",&x); z=max_prime(x); printf("%d数値以下で最大の素数は[%d]である！\n",x,z); return 0; }
素数の分類に関して

前回質問させていただいた証明に関することなのですが、最後の一文が分からないためもう一度質問させていただきます。［類題］　「8n + 3 型の素数は無限に多くある事を示せ。」の略解。＊）文中のｐ＾は複素数ｐの共役な複素数です。例えば、ｐ＝１＋iの場合、ｐ＾は１－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が素数でないならば矛盾はしてないのでしょうか。よろしくお願いします。
素数の分類に関して

［類題］　「8n + 3 型の素数は無限に多くある事を示せ。」の略解。＊）文中のｐ＾は複素数ｐの共役な複素数です。例えば、ｐ＝１＋iの場合、ｐ＾は１－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) となり有限性に矛盾。故にこの型の素数は無限個。この証明における、この因子は PP^ の中では偶数冪で出てくるから、その部分は 8n + 1 型である。がなぜ言えるのかという点と最後の一文である素元分解の一意性により、N( a + b √2 i ) = a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8) となり有限性に矛盾。における a2 + 2b2 は素数であり a2 + 2b2 ≡ 3 (mod. 8）がなぜ分かるのかが理解できません。よろしくお願いします。

メルセンヌ数

みんなの回答

補足 2012/11/05 23:35

関連するQ&A

素数

立法数=立法数×立法数

素数で困ってます

素数　再帰関数

素数　無限

素数は無限

素数定理をこのように解釈しても良いか。

素数は無限に存在する

素数？？

素数の分類と無限性に関して。

素数　反例

【C→JAVA】素数の組の数を求めるプログラム

素数の分類と無限性に関して。以前質問させていただいたことの延長になりま

素数の判定

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

ユークリッドの素数無限の証明を教えて

独習C　素数テスタ・・・分からない

C言語の素数判定について質問です。

素数の分類に関して

素数の分類に関して

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

メルセンヌ数

みんなの回答

補足 2012/11/05 23:35

関連するQ&A

素数

立法数=立法数×立法数

素数で困ってます

素数 再帰関数

素数 無限

素数は無限

素数定理をこのように解釈しても良いか。

素数は無限に存在する

素数？？

素数の分類と無限性に関して。

素数 反例

【C→JAVA】素数の組の数を求めるプログラム

素数の分類と無限性に関して。以前質問させていただいたことの延長になりま

素数の判定

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

ユークリッドの素数無限の証明を教えて

独習C 素数テスタ・・・分からない

C言語の素数判定について質問です。

素数の分類に関して

素数の分類に関して

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

素数　再帰関数

素数　無限

素数　反例

独習C　素数テスタ・・・分からない

カテゴリ
一覧

専門家に質問してみよう
専門家登録