- ベストアンサー
任意の正の整数Mに対して、M＜ｇ_p＜ｐ－１となる無限に多くの素数ｐが存在する
- みんなの回答 （4）
- 専門家の回答
質問者が選んだベストアンサー
まず注意 「最小といいますか最小の原始根は１だろうと思いますが」 とありますが、全く違います。 自然数aが素数pの原始根となるとは p-1乗して初めてa^(p-1)≡1 (mod p)となることをいいます。 (よって、a,a^2,…a^(p-2)はmod pで1と合同ではありません) したがって、1^1≡1 (mod p)となるから 1はpの原始根にはなりえません。
その他の回答 (3)
- yoikagari
- ベストアンサー率50% (87/171)
No.２の訂正 「その前に二つのことを確認」 ではなく 「その前に五つのことを確認」
- yoikagari
- ベストアンサー率50% (87/171)
最後にp≡1 (mod m)となる素数が無数に存在すること(Dirichletの素数定理の特別な場合)の証明が書かれたページへのリンクを張っておきます。
- yoikagari
- ベストアンサー率50% (87/171)
「任意の正の整数Mに対して、M＜g_p＜p-Mとなる最小の原始根g_pが取れる無限に多くの素数pが存在する」ことを証明します。 その前に二つのことを確認 (1) (a/p)をルジャントルの記号とします。 (a/p)=1となるとき、aはpの原始根ではない。 (1)の説明 a^{(p-1)/2}≡1 (mod p)となるのでaの位数は(p-1)/2の約数となるからです。 pの原始根gの位数はp-1です。 (1)の説明ここまで (2) pをp≡1 (mod 4)となる素数、qも素数とすると (q/p)=(p/q)、(-1/p)=1 (2)の説明 平方剰余の相互法則と第一補充法則より明らか (2)の説明ここまで (3) pをp≡1 (mod 8)となる素数とすると (2/p)=1 (3)の説明 平方剰余の相互法則の第二補充法則より明らか (3)の説明ここまで (4) m≡n (mod p)となるとき、(m/p)=(n/p) (4)の説明 (m/p)≡m^{(p-1)/2}≡n^{(p-1)/2}≡(n/p) したがって、(m/p)=(n/p)となる (4)の説明ここまで (5) (mn/p)=(m/p)*(n/p) (4)の説明 (mn/p)≡(mn)^{(p-1)/2}≡m^{(p-1)/2}*n^{(p-1)/2}≡(m/p)*(n/p) したがって、(mn/p)=(m/p)*(n/p)となる (4)の説明ここまで さて、「任意の正の整数Mに対して、M＜ｇ_p＜ｐ－１となる無限に多くの素数ｐが存在する」ことを証明します。 「q_1、…、q_kをM以下の奇数の素数します。 p≡1 (mod 8*q_1*…*q_k )…※ となる素数pをとると (2/p)=…=(M/p)=( (p-2)/p)=…=( (p-M)/p)=1となること」…○ を示します。 2≦a≦Mとなる自然数aをとる ○の証明に、上で説明した(2)～(5)を説明なしで用います ○の証明ここから aが奇数のとき a=Πq_i(q_iの積の意味) (a/p)=Π( (q_i)/p)=Π(p/(q_i) )=Π(1/(q_i) )=1 ( (p-a)/p)=( (-a)/p)=(-1/p)(a/p)=1*1=1 aが偶数のとき a=(2^n)*b(bは3以上の整数)のとき b=Πq_i (a/p)=(2/p)^n*Π( (q_i)/p)=Π(p/(q_i) )=Π(1/(q_i) )=1 a=2^nのとき (a/p)=(2/p)^n=1 ( (p-a)/p)=( (-a)/p)=(-1/p)(a/p)=1*1=1 したがって、pを※のように取ると (2/p)=…=(M/p)=( (p-2)/p)=…=( (p-M)/p)=1となることがわかる。 ○の証明ここまで 上で注意した(1)より、1,2,…,M,p-M,p-M+1,…,p-1はpの原始根にはなりえません。 Dirichletの素数定理より※のような素数は無数に取れます。 よって、○より任意の正の整数Mに対して、M＜g_p＜p-Mとなる最小の原始根g_pが取れる無限に多くの素数pが存在することがいえました。
関連するQ&A
- 素数は無限に多く存在することの証明（ユークリッドの別証）を二つの添削
ユークリッドの証明は背理法を用いた証明。 素数を有限個とするならその最大素数を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つの証明はこれであっているでしょうか？
- ベストアンサー
- 数学・算数
- 以下の(1)、(2)を用いて、背理法により素数が無限個存在
以下の(1)、(2)を用いて、背理法により素数が無限個存在することを示せ。 (1)正の実数rについて、無限級数Σ_[k=1]^[∞] 1/(k^r)はr>1のとき収束する。 (2)mを正の整数、p_1, p_2, ..., p_mを相異なる素数とし、Λ={(k_1, k_2, ..., k_m)|k_i∈Z, k_i≧0, 1≦i≦m}とする。このとき、無限級数Σ_[(k_1, k_2, ..., k_m)∈Λ] 1/[(p_1^(k_1)) (p_2^(k_2))... (p_m^(k_m))]は収束する。 この問題の解き方がわかりません。教えて下さいませんか。
- ベストアンサー
- 数学・算数
- メルセンヌ素数でない素数は無限に存在するか？
素数は無限に存在することが知られています。 ユークリッドやオイラーの証明があります。 また、コンピュータでは、大きい素数を探すときに、 メルセンヌ素数を探します。 しかし、メルセンヌ素数は無限にあるかどうかわかりません。 ここで、質問です。 メルセンヌ素数でない素数は、無限にあるのでしょうか？ 素数はメルセンヌ素数かメルセンヌ素数でない素数のどちらかです。 その二種類を合わせると、無限個ありますから、 メルセンヌ素数が有限個ならば、メルセンヌ素数でない素数は無限個あるとわかります。 でも、メルセンヌ素数は有限個しか見つかっていないだけで、 本当に有限個かどうかはわかりません。 メルセンヌ素数でない素数が無限個あるかどうかもわからないのではないでしょうか？ それとも、他の方法で、わかるのでしょうか？ 例えば、メルセンヌ数（素数とは限らない）とメルセンヌ数（素数とは限らない）の間には、 ２個以上のメルセンヌでない素数が存在することがわかっているとか。 でも、ずっと先に行くと、素数はすべてメルセンヌ素数になっているということは 考えられないでしょうか？ しかし、双子素数が無限に存在するならば、メルセンヌ素数でない素数が無限に存在しそうですね。 双子素数より弱くても、よさそうですね。 素数分布とか考えると、どうなるのでしょうね。 やっぱり、メルセンヌ素数でない素数は無限個あるような気がしてきました。
- ベストアンサー
- 数学・算数
- 自然数の組には無限の降下列が存在しない？
自然数の組に対して、辞書式順序≫を次のように定義する。 (n1,m1) ≫ (n2,m2) ⇔ n1>n2 または (n1=n2 かつ m1>m2) すると、 (n1,m1) ≫ (n2,m2) ≫ (n3,m3) ≫ ... となるような無限降下列は存在しないことがいえる。 直感的に，(N,N)は無限に存在するから降下列は無限にある気がするのですが，なぜ無限にならないのでしょうか？
- 締切済み
- 数学・算数
- 行列Mの最小多項式pの存在証明
こんにちは皆様いかがお過ごしでしょうか? [問]与えられた行列Mが最小多項式pの解であるようなpの存在を示せ。 に難儀しております。どうぞご教示ください。 因みに最小多項式とは正方行列Aに対してf(A)=Oとなる多項式f(x)の内で次数が最低 で最高次の係数が1であるものをAの最小多項式といい,m_A(x)で表す。 です。
- ベストアンサー
- 数学・算数
- 素数の分類と無限性に関して。
素数の分類と無限性に関して。 ※＾は乗数の意味です。 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) となる」の部分がどのようにして言えるのかが分かりません。フェルマーの小定理を用いているのでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素数と組み合わせの問題
Z会の問題なのですが、わからないところがあるので質問します。 nは素数pと自然数mを用いて、n=p^mと表される数であるとする。このとき、次の各問に答えよ。 (1)r=1,2,・・・,n-1のとき、nCrはpの倍数であることを示せ。 (2)nと(2^n)-1は互いに素であることを示せ。 nCrが自然数であることなら帰納法でなんとかなると思ったのですが、pの倍数になることがどうしても証明できません。どなたか教えてください。
- ベストアンサー
- 数学・算数
- 中国の剰余定理と原始根
アドバイスよろしくおねがいします。 p,ｑを素数としたときに mod p と mod q において 原始根になる値gが存在する。それは中国剰余定理からいえる。 という記述があったのですが、原始根と中国剰余定理が結びつきません。 mod p,mod q において原始根ということは gを法pにおいてp-１乗してはじめて１になり、かつ法qにおいてもq-1乗してはじめて１になるわけだと思います。（ほかにも条件がありますが…） で、中国剰余定理は 簡単に言うと 複数の法が違い、法の数が互いに素な連立合同式に対して、解が一意に定まるということだと思います。 この二つが結びつきません。 ご教授お願いします
- ベストアンサー
- 数学・算数
- 素数の分類と無限性に関して。以前質問させていただいたことの延長になりま
素数の分類と無限性に関して。以前質問させていただいたことの延長になります。 ※＾は乗数の意味です。 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の位数が８と考えています。ｐが素数で、８はｐ－１の約数になるとの考えは当っているでしょうか・・？ よろしくお願いします。
- ベストアンサー
- 数学・算数
お礼
そうでした、ありがとうございました。 すごい、間抜けに我ながら反省しました。