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

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

No.4 ベストアンサー 回答者： nagata 回答日時： 2001/09/22 20:56

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

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

この回答へのお礼

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

お礼日時：2001/09/25 16:17

No.5 回答者： stomachman 回答日時： 2001/09/23 21:28

考えすぎ？

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

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

この回答へのお礼

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

お礼日時：2001/09/25 16:19

No.3 回答者： million-show 回答日時： 2001/09/21 00:22

２＾１－１＝１

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

No.2 回答者： ranx 回答日時： 2001/09/20 19:02

#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 回答日時： 2001/09/20 16:42

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

１３です

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

この回答へのお礼

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

お礼日時：2001/09/20 17:20