- ベストアンサー
nが素数であるかどうかの判定
素数判定の勉強をしています。 次の文の内容が成立する理由がわかりませんでした。 -----内容----- n-1 = 2^(t-1) * m としたとき とある整数a (aは2以上n-2以下)において もし a^{(2^j)*m} ≡ 1 mod n かつ a^［{(2^(j-1)}*m] ≠ ±1 mod n ならば a^［{(2^(j-1)}*m] -1 と nの自明でない最大公約数がみつかりnは素数ではないと判断できる。 (ここで、jは1以上t-1以下の自然数。また記号「≠」を「not 合同」の意味で使用しています。) -----終了----- これはなぜなのでしょうか？ なぜ公約数が見つかるのでしょうか？ アドバイスよろしくお願いします。
- ilnmfay
- お礼率75% (137/181)
- 数学・算数
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
整数nの素数判定にはフェールマーの小定理を応用したもう少し簡単なフェールマーテストがありますよね。 a<nに対して a^(n-1)≠1 (mod n)ならばnは合成数 というものです。 ところがこの判定法はnが素数である必要条件を与えるだけで、十分条件を与えるものではありません。 現にn以下の全てのaに対してa^(n-1)≡1 (mod n)であるにもかかわらず素数でないような数が存在し、カーマイケル数(擬素数)と呼ばれています。 小さい方から挙げると561,1105,1729,...です。 このようなカーマイケル数にも対応して合成数だと判定する判定法としてラビン・ミラー(Rabin-Miler)判定法があります。 質問者様が書かれているのはまさにその判定法のように思います。 この判定法の証明は、webなどで検索して貰えれば見つかると思います。 しかしラビン・ミラー判定法にたいしても、合成数であるにも関わらす判定を通過する数として強擬素数が存在します。 また『なぜ公約数が見つかるのでしょうか？』と書かれていますが、フェールマーテストにしてもラビン・ミラーテストにしてもこれらの方法で具体的な約数がわかるわけではありません。 だからこそ「"自明でない"最大公約数がみつかり」と書かれています。 約数があることはわかるんだけど顔までは見えないという状態です。 これらのテストは、nが素数である必要条件を満たさないために合成数であると判定するだけで、具体的な約数を見つけるのには全く役に立ちません。
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
いろいろな考え方はあると思うけど, 「p が素数なら ab ≡ 0 → a ≡ 0 または b ≡ 0」だから, x^2 ≡ 1 (mod n) かつ x ≠ ±1 (mod n) であるような x が見付かれば n は合成数です. しかも x-1 や x+1 は n と自明でない公約数を持つことも簡単にわかります (x-1 が n と自明でない公約数を持たないなら x+1 が n の倍数にならないといけないので). で, これで合成数だとわかれば「約数」は見付かりますね＞#1. 「素因数」が見付かるとは限りませんが.
関連するQ&A
- 離散数学の証明問題
離散数学の証明問題 合同でないことを≡×と表します。 Pを素数とし、a≡×0(mod p)とする。また、aの位数をdとする。 このとき、次のことを示せ。 (1)整数nに対して、a^n≡1(mod p)であるならば、かつそのときに限り、d|n (2)dはp-1の約数である。 (3)整数i,jに対してa^i≡a^j (mod p)であるならば、かつそのときに限り、i≡j(mod p) (1)はFermatの小定理を使うと思うのですが、いまいち解法が浮かびません。 (2)はFermatの小定理から自明に思えますが、厳密に証明しないといけないみたいです。 (3)は証明方法がまったく分かりません。 分かる方、証明お願いします。
- ベストアンサー
- 数学・算数
- ｎから２ｎの間に奇素数が全く存在しない区間があるとすると，
ｎから２ｎの間に奇素数が全く存在しない区間があるとすると， それは，どの様なｎになりますか？ ただし，ｎは正の整数です． 無限に近い非常に大きな自然数列の中に，奇素数が全く存在しない膨大な区間があるといわれます．しかも，その区間は，幾らでも大きく取れると聞いたことがあります．そこで，上記の質問がでたわけです． 一応，この質問を命題の形に書いておきます． （１） ｎ を正の整数とする．ｎ＝1, 2, 3, ・・・． ｎ∈Ｎ（自然数全体の集合） （２） ｍ を正の整数とし，ｍ は ｎ＜ｍ＜２ｎ を満たすとする． （３） 集合Ａ(ｎ)を以下のように定義する．ｎを或る値に固定した時， Ａ(ｎ)＝{ ｍ | ｍ,ｎ∈Ｎ, ｎ＜ｍ＜２ｎ} Ａ(ｎ) の 元 ｍ∈Ａ(ｎ) は，ｍ＝ｎ＋１，ｎ＋２, ｎ＋３，・・・ ・・・ ２ｎ－２，２ｎ－１ となる． ●命題：集合Ａ(ｎ)の全ての元 ｍ∈Ａ(ｎ)が奇素数でないような，十分大きな正の整数ｎが存在する． この命題は，成り立つでしょうか？ 成り立たないでしょうか？ ご教授下さい．また，単なるご意見でもかまいませんので，お寄せ下さい． （参考）：仮に，ｎ＝10 とすると，10 と 20 との間には，奇素数 11, 13, 17, 19 が存在します．ｎ＝23 とすれば，46 との間には，奇素数 29, 31, 37, 41, 43 が存在します．この様にならない十分大きなｎが存在するでしょうか？ と言うのが，質問の趣旨です．
- ベストアンサー
- 数学・算数
- 二次合同方程式の解法過程について
Mr_Holland さんが以前回答された過程で、 「x≡±1 (mod 3)・・・・（１） ∴x=3n±1」・・・・・・（２） と 「±2n≡2 (mod 3)・・・・（３） この合同式は ±n=1 のとき成立するので・・・（４） ±n=3m+1 （m:整数）とおける。」・・・・・（５） の２つの展開が異なっているのが、よくわかりませんのでご教授願います。 【補足】 前者は展開が納得できるのですが、 後者は、 ±n=1(mod 3)から ⇔n=±1(mod 3)と同じだから、 ⇔n=3m±1と展開できるので、 （5）式±n=3m+1と異なります。 後者の妥当性が知りたいです。 以下、Mr_Holland さんからの 回答 2010-11-17 10:57:57 回答No.2 Mr_Holland ANo.1は煩雑でした。 もう少しスマートに計算することができましたので、以下に示します。 x^2≡7 (mod 27) ⇒x^2≡7 (mod 9) ⇒x^2≡1 (mod 3) ⇔x≡±1 (mod 3) ∴x=3n±1 (n:整数）とおける。 以下、複号同順とします。 x^2=(3n±1)^2= 9n^2±6n+1 だから x^2≡±6n+1≡7 (mod 9) ∴±6n≡6 (mod 9) ∴±2n≡2 (mod 3) この合同式は ±n=1 のとき成立するので ±n=3m+1 （m:整数）とおける。 x^2=9(3m+1)^2+6(3m+1)+1 =81m^2+72m+16 だから x^2≡18m+16≡7 (mod 27) ∴18m+9≡0 (mod 27) ∴2m+1≡0 (mod 3) この合同式は m=1 のとき成立するので m=3k+1 （k:整数）とおける。 x=3n±1=±(±3n+1)=±{3(3m+1)+1}=±(9m+4)=±{9(3k+1)+4}=±(27k+13) ∴x≡±13 (mod 27) ∴x≡13,14 (mod 27)
- 締切済み
- 数学・算数
- 線形合同式と数列周期
a,b,kを a≡1(mod4)、bと2との最大公約数が1、k>=2 を満たす自然数とすると、 線形合同式 x_(n+1)≡a*(x_n)+b mod 2^k ただし 0<= (x_n) <2^k で定義される0から(2^k)-1の間の整数による数列{x_n} は、任意の初期値x_0 に対して 周期が2^kであることを示せ。 わかりません。。よろしくお願いします！！
- ベストアンサー
- 数学・算数
- 最大公約数、定理の証明
a,bを a=b=0 でない2つの整数とするとき a*r + b*s =(a,b) のような整数 r,s が存在する --------------------------------------- という定理があって、この定理を使って 次の定理を証明せよ、という問題なのですが… d=(a,b) 整数 n は、 n|d のとき、その時に限り a と b の公約数である … n|d は dはnで割り切れるという意味 どういうふうに導くのかわかりません。 d=(a,b)= a*r + b*s = t*n (tは整数) とおく、ここまで何となくやってみたのですが… 「公約数」であることを示す方法、目標が見えません。 教えてください。
- ベストアンサー
- 数学・算数
- 互いに素の問題です！
2つの整数mとnが互いに素のとき、nとm－nも互いに素であることの証明で、答えはnとm－nの最大公約数をｇとおくとn＝aｇ、m－n＝bｇ(a、bは互いに素な整数)とおけて、m＝n＋(m－n)＝(a＋b)ｇとなる n＝aｇとm＝n＋(m－n)＝(a＋b)ｇよりmとnとはｇを公約数にもつがm、nは互いに素だからm、nの正の公約数は1しかない よってｇ＝1よりnとm－nは互いに素 としてるのですが、 「n＝aｇとm＝n＋(m－n)＝(a＋b)ｇよりmとnとはｇを公約数にもつがm、nは互いに素だからm、nの正の公約数は1しかない」 という部分の意味が分からないので詳しく教えてください！ちなみに互いに素とか公約数とかの意味はわかります！
- ベストアンサー
- 数学・算数
- フェルマの小定理と位数に関する質問です
問題） pを素数とします。また、aをpで割り切ることのできない整数とします。 この時、a^n≡1(mod p)となる最小の正整数nをmとすると p≡1(mod m)であることを証明したいです。 証明) まず、フェルマの小定理より、 n=p-1のとき、a^n≡1(mod p)が成り立つことが分かります。 よって、n=p-1がa^n≡1(mod p)となる最小の正整数nの場合、 m=p-1なので、明らかにp-1をmで割り切ることができるため、 p≡1(mod m)である。 (ここからが分かりません。。。) 次に、n=p-1がa^n≡1(mod p)となる最小の正整数nでない場合、 つまり、m<p-1となるmが存在する場合、 そのmによって、p≡1(mod m)が成り立つことを証明したいのですが、よく分かりません。 どなたか詳しい方、ご教授お願いします。 途中までの証明も不適切(不要)でしたら指摘してください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 素数の判定
自然数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で割り切れると何が不合理なのかと、自分の証明の方針のまちがいを指摘してください、お願いします。
- ベストアンサー
- 数学・算数
