- ベストアンサー
メルセンヌ数の性質と計算方法とは？
FT56F001の回答
- FT56F001
- ベストアンサー率59% (355/599)
1)だけ フェルマーの小定理 qが素数のとき，a^(q-1)≡1(mod q) でa=2とする。 http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Fermat.html http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86
関連するQ&A
- 最大公約数を求めたい！
二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか？？ ＜さらにもし出来る方がおられたら…＞------------------------------------ 実は最終的にはある数（a（素数））があって、そのaと”たがいに素”である数（ｂ）をプログラムで求めたいんです…。 ある本によると適当な二つの素数ｐ、ｑがあるとしてこのふたつの積（つまりｐ＊ｑ）をｍとします。また、(p-1)(q-1)＝aとすると ”gcd(b,a)≡1(mod m)” という式を満たすんだそうです…。 ※この中にでてくる値で実際に分からないのは"b"のみです。 ※ここで書いているgcd(b,a)というのはaとｂの最大公約数のことです。 --------------------------------------------------------------------- かなり難しいのでこの質問の回答をいただくと本当に助かります。 よろしくお願いしますm(_ _)m
- ベストアンサー
- Visual Basic
- 任意のkに対し、f(m）がk個の素因数を持つ様なm
f(x)を整数係数のmonic polynomialとしたとき 任意の整数kに対して、f(m)がk個の異なる素因数をもつような整数mは存在するか という問題なのですが、 素数を小さい順にp_1 ,p_2, p_3, ...とし、 f(m)の素因数がp_1, p_2, ... , p_kとなるようなmが存在することを示す。 f(x)は問題文の条件より f(x)=(x-a_1)(x-a_2)....(x-a_n)とおける (a_iは整数） p_iは素数なので互いに素 中国の剰余定理より y≡a_1 (mod p_1) y≡a_2 (mod p_2) y≡a_3 (mod p_3) ... y≡a_k (mod p_k) を満たすｙが存在する。 y-a_1≡0 (mod p_1) y-a_2≡0 (mod p_2) y-a_3≡0(mod p_3) ... y-a_k≡0(mod p_k) となるためf(y)はp_1, p_2, ..., p_kのすべてで割り切れる。 間違いがあったら指摘ください。
- ベストアンサー
- 数学・算数
- 合同式の証明について
自分の使っている参考書に書かれている合同式の証明で a≡c (mod m) b≡d (mod m)より a-c=mp b-d=mq (p,qは整数)とおくことが出来る。 よって (a+b)-(c+d)=(a-c)+(b-d)=mp+mq=m(p+q) (a-b)-(c-d)=(a-c)-(b-d)=mp-mq=m(p-q) ab-cd=(c+mp)(d+mq)-cd=m(cq+pd+mpq) ゆえに(a+b)-(c+d),(a-b)-(c-d),ab-cdはmの倍数であるから a+b≡c+d(mod m) a-b≡c-d(mod m) ab≡cd(mod m) は成り立つ。 と書かれているのですが、全体的によく理解が出来ません。 まず なぜ a≡c (mod m) b≡d (mod m) であれば a-c=mp b-d=mq (p,qは整数)と、おくことが出来るのかということと ab-cdからどのような計算をすると(c+mp)(d+mq)-cd このようになるのかもわかりません。 数学はあまり得意ではないので中学生レベルの学力でも理解できるように 説明していただけると有り難いです。
- ベストアンサー
- 数学・算数
- 最大公約数 gcd(a,b,c) と一次合同式の解の存在
初等整数の証明で困ってます。 (1)gcd(a,b,c)はgcd(a,b)の約数であることを証明せよ。 (2)gcd(gcd(a,b),c)はgcd(a,b,c)の倍数であることを証明せよ。 また合同式の定理の証明について gcd(a,b)=1ならばax≡c(mod b)は解をもつ。 さらにこの合同方程式の一つの解をpとすると、すべての整数kについてp+kb も解である。逆にこの合同方程式の任意の解はp+kb と表わされる。 ax≡c(mod b) は b | (ax-b) を導けばよいのでしょうか？ お願いします。
- 締切済み
- 数学・算数
- 最大公約数と最小公倍数の関係
ある二つの正の整数の最大公約数と最小公倍数をかけたものは、元の二つの数字をかけたものと等しいっていうことは言えますか？ つまり、最大公約数をgcd、最小公倍数をlcmとあらわすことにして、 正の整数ｍとｎについて、 gcd（m , n）・lcm（m , n）＝m・n は成り立つかどうかを教えてください。 できればその理由（証明）も添えてください。 協力お願いします！！
- 締切済み
- 数学・算数
- フェルマの小定理と位数に関する質問です
問題） 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)が成り立つことを証明したいのですが、よく分かりません。 どなたか詳しい方、ご教授お願いします。 途中までの証明も不適切(不要)でしたら指摘してください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 最大公約数 証明
整数(環？)についての証明がわからないので質問します。 証明することは、 p,qを2整数(または数体Kにおけるxの整式)とし、式 pu+qv・・・(1)においてu及びvを整数(Kにおける整式)全体にわたって変ずるものとする。かくして得る整数(整式)の中の最小正の整数(xについての最低次の整式)をdとし、d=pu0+qv0・・・（2）とする。然るときdはp,qの最大公約数である。 です。証明は以下のように書いてあります。 実際d'がp,qの公約数ならば、(2)からd'はdの約数である。他方dはu,vのいかんを問わず常に(1)を割り切っている。何となれば(1)をdで除した剰余をr(rは０に等しくない) とすれば、 pu+qv=ad+r=a(pu0+qv0)+r つまりp(u-au0)+q(v-av0)=r ところでｒはdより小なる正整数(dより低次の整式)であるから、上の関係はdが(1)が最小(最低次)であるという仮定に矛盾する。故にu,vのいかんを問わずdは(1)を整除する。今u=1,v=0とおけば(1)はpとなり,u=0,v=1とおけば(1)はqとなるから,dはpをもqをも割り切る。それゆえdはp,qの最大公約数である。 自分は、2*1+3*2＝8などから、8は2と3の最大公約数ではないと思い。何かp,u,q,v に条件があるのではと考えましたが、整数という条件しか探せませんでした。 剰余をｒとした後の計算と、剰余ｒを仮定すると矛盾するからｒ＝0ということ、ぐらいしかわかりません。ヒントでもよいので教えてくださいお願いします。
- ベストアンサー
- 数学・算数
- RSA暗号の中国剰余定理についておしえてください.
RSA暗号の中国剰余定理についておしえてください． N=77 = 7×11, p1=7, p2=11 d1 = d mod (p1-1) = 43 mod (7-1) = 1 d2 = d mod (p2-1) = 43 mod (11-1) = 3 m1 = c^d1 mod p1 = 48^1 mod 7 = 6 m2 = c^d2 mod p2 = 48^3 mod 11 = 4^3 mod 11 = 9 連立方程式 m = 6 mod 7 m = 9 mod 11 となり p1=7とp2=11は共に素数であるので互いに素 q1=p2^-1 mod p1 = 11^-1mod 7=4^-1mod 7=2 /// q2=p1-^1 mod p2 = 7^-1mod 11=8 //// これを用いて m=(m1×p2×q1 + m2×p1×q2) mod p1p2 = (6×11×2 + 9×7×8) mod 77 = (132+504) mod 77 = 20 平文 m = 20 とあるのですが，q1=p2^-1 mod p1 = 11^-1mod 7=4^-1mod 7=2と q2=p1^-1 mod p2 = 7^-1mod 11=8の部分でどうして2と8になるのかがわかりません．1時間くらい悩んでいるのですが見当がつきません．教えて下さい．＞＜
- 締切済み
- その他([技術者向] コンピューター)