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

質問

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

回答No.4

nagata · ベストアンサー

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で割ることができます。

どうでしょうか、すこしはからくりが分かったでしょうか。
どうやら僕もノウタリンなようであんまりちゃんと一般的な式にできません。
ご勘弁を。

お礼

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

回答No.5

stomachman

考えすぎ？
　単純にユークリッドの互除法を用いれば良いのでは？
　ユークリッドの互除法は
<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)>→ 終わり。

"="の左辺のカッコはずして展開すれば右辺になります。

お礼

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

回答No.3

million-show

２＾１－１＝１
２＾２－１＝３
２＾３－１＝７
２＾４－１＝１５
２＾５－１＝３１
２＾６－１＝６３
２＾７－１＝１２７
２＾８－１＝２５５
２＾９－１＝５１１
２＾１０－１＝１０２３
…
と続けていくとわかると思いますが
例えば２＾６－１の６３の約数は３，７，２１の３種類で
その中に２＾２－１の３と２＾３－１の７が入っています。
これは６の約数が２，３だからです。
もちろん２＾１０－１の１０２３の約数の中には
２＾５－１の３１が入っています。
って
私ノウタリンなので式でできません（笑）
ご勘弁を

回答No.2

ranx

#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

million-show

９１と６５の最大公約数は
１３です

２＾１３－１が８１９１です。

お礼

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