OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

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

  • 暇なときにでも
  • 質問No.138739
  • 閲覧数235
  • ありがとう数3
  • 気になる数0
  • 回答数5
  • コメント数0

お礼率 83% (10/12)

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

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

  • 回答No.4
レベル8

ベストアンサー率 33% (10/30)

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

お礼率 83% (10/12)

なるほど、そういうことだったんですね。
よくわかりました。ありがとうございます。
投稿日時 - 2001-09-25 16:17:36
-PR-
-PR-

その他の回答 (全4件)

  • 回答No.1
レベル9

ベストアンサー率 15% (18/120)

91と65の最大公約数は 13です 2^13-1が8191です。 ...続きを読む
91と65の最大公約数は
13です

2^13-1が8191です。
お礼コメント
ugoo

お礼率 83% (10/12)

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


  • 回答No.2
レベル13

ベストアンサー率 24% (357/1463)

#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) ...続きを読む
#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.3
レベル9

ベストアンサー率 15% (18/120)

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^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が入っています。
って
私ノウタリンなので式でできません(笑)
ご勘弁を
  • 回答No.5
レベル14

ベストアンサー率 57% (1014/1775)

考えすぎ?  単純にユークリッドの互除法を用いれば良いのでは?  ユークリッドの互除法は <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 ...続きを読む
考えすぎ?
 単純にユークリッドの互除法を用いれば良いのでは?
 ユークリッドの互除法は
<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

お礼率 83% (10/12)

こんな方法があったんですか・・・知りませんでした。
いい勉強になりました。ありがとうございます。
投稿日時 - 2001-09-25 16:19:24
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ