• ベストアンサー

2^91-1と2^65-1の最大公約数

2^91-1と2^65-1の最大公約数を求めるにはどうすればいいのですか? これほど大きな値だと共通の素数で割ることもユークリッドの互除法も使えそうにありません。 ちなみにコンピュータに解いてもらったら GCD(2^91-1,2^65-1)=8191 でした。

  • ugoo
  • お礼率83% (10/12)

質問者が選んだベストアンサー

  • ベストアンサー
  • nagata
  • ベストアンサー率33% (10/30)
回答No.4

No.3の答えに対する考察です。 まず2^n-1=Σ_(0<=i<=n-1)2^i--(*)という等式があります。 等比数列の和の式です。 これを利用すると例えば 2^6-1=(2^5)+(2^4)+(2^3)+(2^2)+(2^1)+(2^0) となります。 これを2個づつまとめると {(2^5)+(2^4)} + {(2^3)+(2^2)} + {(2^1)+(2^0)}= (2^4)*{(2^1)+(2^0)}+(2^2)*{(2^1)+(2^0)}+{(2^1)+(2^0)}= {(2^1)+(2^0)}{(2^4)+(2^2)+(2^0)}となります。 ここでまた(*)を利用すると{(2^1)+(2^0)}=2^2-1となります。 よって2^6-1は2^2-1で割ることができます。 同様に3個づつまとめると {(2^5)+(2^4)+(2^3)} + {(2^2)+(2^1)+(2^0)}= (2^3)*{(2^2)+(2^1)+(2^0)}+{(2^2)+(2^1)+(2^0)}= {(2^2)+(2^1)+(2^0)}{(2^3)+1} ここで(*)を利用すると{(2^2)+(2^1)+(2^0)}=2^3-1となります。 よって2^6-1は2^3-1で割ることができます。 どうでしょうか、すこしはからくりが分かったでしょうか。 どうやら僕もノウタリンなようであんまりちゃんと一般的な式にできません。 ご勘弁を。

ugoo
質問者

お礼

なるほど、そういうことだったんですね。 よくわかりました。ありがとうございます。

その他の回答 (4)

  • stomachman
  • ベストアンサー率57% (1014/1775)
回答No.5

考えすぎ?  単純にユークリッドの互除法を用いれば良いのでは?  ユークリッドの互除法は <p,q> → p>qなら<p-q,q>、p<qなら<p,q-p>, p=qなら終わり。 という変換を繰り返す。  これは適当な正の自然数nについて <p,q> → p>nqなら<p-nq,q>、np<qなら<p,q-np>, p=qなら終わり。 としても全く同じ事。ですから、 <(2^91-1),(2^65-1)>→ <(2^91-1)-(2^26)(2^65-1),(2^65-1)> = <(2^26-1),(2^65-1)>→ <(2^26-1),(2^65-1)-(2^39)(2^26-1)> = <(2^26-1),(2^39-1)>→ <(2^26-1),(2^39-1)-(2^13)(2^26-1)> = <(2^26-1),(2^13-1)>→ <(2^26-1)-(2^13)(2^13-1),(2^13-1)> = <(2^13-1),(2^13-1)>→ 終わり。 "="の左辺のカッコはずして展開すれば右辺になります。

ugoo
質問者

お礼

こんな方法があったんですか・・・知りませんでした。 いい勉強になりました。ありがとうございます。

回答No.3

2^1-1=1 2^2-1=3 2^3-1=7 2^4-1=15 2^5-1=31 2^6-1=63 2^7-1=127 2^8-1=255 2^9-1=511 2^10-1=1023 … と続けていくとわかると思いますが 例えば2^6-1の63の約数は3,7,21の3種類で その中に2^2-1の3と2^3-1の7が入っています。 これは6の約数が2,3だからです。 もちろん2^10-1の1023の約数の中には 2^5-1の31が入っています。 って 私ノウタリンなので式でできません(笑) ご勘弁を

  • ranx
  • ベストアンサー率24% (357/1463)
回答No.2

#1へのお礼に対する回答です。 一般的に成り立つことではないと思いますが、このケースではユークリッドの 互助法が使えます。 まず、(2^13-1)が共通因数であることは明らかですから、両者をこの数で割ってみます。 (2^91-1)=(2^13-1)(2^78+2^65+2^52+2^39+2^26+2^13+1) (2^65-1)=(2^13-1)(2^52+2^39+2^26+2^13+1) ですから、(2^78+2^65+2^52+2^39+2^26+2^13+1)と(2^52+2^39+2^26+2^13+1)に共通の 因数が無いかどうかしらべればよいわけです。 (2^78+2^65+2^52+2^39+2^26+2^13+1)=(2^26)(2^52+2^39+2^26+2^13+1)+(2^13+1) (2^52+2^39+2^26+2^13+1)=(2^39+2^13)(2^13+1)+1 ですから、両者は互いに素です。 つまり、(2^91-1)と(2^65-1)のGCDは(2^13-1)です。

回答No.1

91と65の最大公約数は 13です 2^13-1が8191です。

ugoo
質問者

お礼

回答ありがとうございます。 では、どうして GCD(2^91-1,2^65-1)=2^GCD(91,65)-1 が成り立つと言えるのでしょうか?

関連するQ&A

  • 最大公約数

    素因数分解を使わない最大公約数の求め方で、二つはユークリッドの互除法を利用するというのはわかったのですが、3つはどのようにして求めればいいと思いますか?

  • 最大公約数について

    ユークリッドの互除法について勉強していて 途中で疑問に思ったことがあるのですが 例えば 288と108という数について 288と108の最大公倍数は36 288÷108=2余り72 ここから 108と72を取り出して この二つの数の最大公倍数も36 108÷72=1余り36 ここから72と36を取り出して、 この二つの数の最大公倍数も36 となりますが、なぜ割る数と余りの最大公倍数が、初めの数の最大公約数とずっと同じであり続けるのでしょうか? ユークリッドの互除法自体はある程度理解できています。 ユークリッドの互除法は、この数の動きを利用して最大公約数を求めていくようですが、なぜこのようなことになるのかが知りたいです。 難しい内容では理解できないので、できれば中学生レベルでも理解できるように説明してもらえればありがたいです。

  • 最大公約数から最小公倍数

    ユークリッドの互除法についてなんですが、あるサイトでの公式?というか、 例》aとbの最大公約数を求めろ。 式がr(余り)=a-(a÷b)b それはわかったんです。 ですが、最大公約数から最小公倍数を出すという作業がわかりません。それと、手でやっているのでコンピューターは使っていません。 わかりやすく教えてください!

  • 最大公約数の問題

    公約数と公倍数、という単元の問題なのですが 問2-3が「次の最大公約数を求めよ」というもので (39,18,8) などの問題が出されており、それに続く問題として 問2-4 自然数 a,b,c に対して ((a,b),c)=(a,(b,c)) が成り立つことを示せ。 というものがあります。 最大公約数を使って解く問題だとは予想できるのですが、どのようにすれば証明できるのかが分かりません。 その前の問題では、ユークリッドの互除法を用いて最大公約数を求めていました。 どなたか分かる方がいらっしゃいましたら、ご教授願います。

  • ユークリッド互除法の意義

    2つの数の最大公約数の求め方の1つとしてユークリッド互除法を学習しました。 しかし、最大公約数の求め方は素因数分解でも求められます。 共通に割り切れるもので割っていけばよいので、わざわざユークリッド互除法を使わなくてもいいのでは?と思うのですが、ユークリッド互除法を使うことのよさってあるのですか? 回答よろしくお願いいたします。

  • 最大公約数を求めたい!

    二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか?? <さらにもし出来る方がおられたら…>------------------------------------ 実は最終的にはある数(a(素数))があって、そのaと”たがいに素”である数(b)をプログラムで求めたいんです…。 ある本によると適当な二つの素数p、qがあるとしてこのふたつの積(つまりp*q)をmとします。また、(p-1)(q-1)=aとすると ”gcd(b,a)≡1(mod m)” という式を満たすんだそうです…。 ※この中にでてくる値で実際に分からないのは"b"のみです。 ※ここで書いているgcd(b,a)というのはaとbの最大公約数のことです。 --------------------------------------------------------------------- かなり難しいのでこの質問の回答をいただくと本当に助かります。 よろしくお願いしますm(_ _)m

  • 再帰関数とユークリッドの互除法を用いて最大公約数を求める

    学校の課題で、再帰関数とユークリッドの互除法を用いて10~100000までの最大公約数を求めるという問題が出て自分でプログラムを作ってみたのですが無限ループに入ったり、関数が使えてないみたいでできません。プログラムを見て頂いて、どこを改善したらいいかを教えてください。 #include <stdio.h> /* 正整数 n, m の最大公約数を計算する */ int gcd(int n, int m) { int res; res = n % m; if (res == 0) return m; /* 最大公約数が求まった */ return gcd(m, res); /* 再帰呼び出し */ } int main(void) { int i,j; for(i=10000;i>=10;i--){ for(j=10;j=10000;j++){ printf("%d to %d no saidaikouyakusuu ha %d \n", i, j, gcd(i, j)); } } return (0); } です。期限が今日の夜までで、ぎりぎりなんですがよろしくお願いします。

  • 最大公約数の証明

    a,b>1の時、gcd(a,b)=dならばgcd(a^2,b^2)=d^2となるのを説明せよ。 っていう問題で、説明の仕方がわかりません。 aが例えば2*3=6で、bが2*3*3=18だとすれば公約数は2*3で、aとbを2乗すると2^2*3^2と2^2*3^4になって共通なのは公約数の2乗になるからって・・・説明にもなってないようなことしか思い浮かびません・・・。 よろしくおねがいします。

  • ユークリッドの互除法について

     ユークリッドの互除法を使って最大公約数、整数解を求められると聞いたのですが、イマイチ要領がつかめません。    もしよろしければ、どなたかユークリッドの互除法での最大公約数、整数解の求め方を教えてください。

  • 最大公約数??

    今日のyahooニュースで厚生事務次官の事件で 見出しに"異例の警戒=最大公約数で展開" や本文に警察当局の話として”今後も発生が懸念され、最大公約数で捜査と警戒を展開する必要がある”というのが載っていました。 このときの最大公約数とはどういう意味ですか。 yahoo辞書で調べたのですが、最大公約数には 1 《 greatest common measure 》二つ以上の自然数の公約数の中で最大のもの。 2 種々の意見の間にみられる共通点。「多くの発言の中から―を出す」 という2つの意味があり、今回の場合はまず1は違うのはすぐわかるのですが、2でもよく意味がわかりません。 単に"最大規模"の誤りでしょうか? よろしくお願いします。