最新閲覧日:

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

A 回答 (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)>→ 終わり。

"="の左辺のカッコはずして展開すれば右辺になります。
    • good
    • 0
この回答へのお礼

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

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

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

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

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

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

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が入っています。
って
私ノウタリンなので式でできません(笑)
ご勘弁を
    • good
    • 0

#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)です。
    • good
    • 0

91と65の最大公約数は


13です

2^13-1が8191です。
    • good
    • 0
この回答へのお礼

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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ