- 締切済み
メルセンヌ数
定理の証明 もともと英語の文です。（教科書が英語） 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 である。と訳しました 証明がわからなくて困ってます。どなたかわかりやすく証明教えてください（＞＜）
- みんなの回答 （2）
- 専門家の回答
関連するQ&A
- 素数 再帰関数
メイン #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が求められますがアルゴリズム理解できません。この２つの関数のアルゴリズムについて、ご教授ください。め
- 締切済み
- C・C++・C#
- 素数 無限
「素数は無限にある」証明について。（たびたびすみません） 素数が有限個で 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のいずれとも異なる． これは矛盾である。したがって定理が証明された． なんかすっきりしなて非常に困ってます。誰か教えてください。お願いします。
- ベストアンサー
- 数学・算数
- 素数の分類と無限性に関して。
素数の分類と無限性に関して。 ※＾は乗数の意味です。 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) となる」の部分がどのようにして言えるのかが分かりません。フェルマーの小定理を用いているのでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
補足
もう少し詳しくお願いします(>_<)