- ベストアンサー
2^91-1と2^65-1の最大公約数
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で割ることができます。 どうでしょうか、すこしはからくりが分かったでしょうか。 どうやら僕もノウタリンなようであんまりちゃんと一般的な式にできません。 ご勘弁を。
関連するQ&A
- 最大公約数について
ユークリッドの互除法について勉強していて 途中で疑問に思ったことがあるのですが 例えば 288と108という数について 288と108の最大公倍数は36 288÷108=2余り72 ここから 108と72を取り出して この二つの数の最大公倍数も36 108÷72=1余り36 ここから72と36を取り出して、 この二つの数の最大公倍数も36 となりますが、なぜ割る数と余りの最大公倍数が、初めの数の最大公約数とずっと同じであり続けるのでしょうか? ユークリッドの互除法自体はある程度理解できています。 ユークリッドの互除法は、この数の動きを利用して最大公約数を求めていくようですが、なぜこのようなことになるのかが知りたいです。 難しい内容では理解できないので、できれば中学生レベルでも理解できるように説明してもらえればありがたいです。
- ベストアンサー
- 数学・算数
- 最大公約数から最小公倍数
ユークリッドの互除法についてなんですが、あるサイトでの公式？というか、 例》ａとｂの最大公約数を求めろ。 式がr(余り)＝a-(a÷b)b それはわかったんです。 ですが、最大公約数から最小公倍数を出すという作業がわかりません。それと、手でやっているのでコンピューターは使っていません。 わかりやすく教えてください！
- ベストアンサー
- 数学・算数
- ユークリッド互除法の意義
２つの数の最大公約数の求め方の１つとしてユークリッド互除法を学習しました。 しかし、最大公約数の求め方は素因数分解でも求められます。 共通に割り切れるもので割っていけばよいので、わざわざユークリッド互除法を使わなくてもいいのでは？と思うのですが、ユークリッド互除法を使うことのよさってあるのですか？ 回答よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 最大公約数を求めたい！
二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか？？ ＜さらにもし出来る方がおられたら…＞------------------------------------ 実は最終的にはある数（a（素数））があって、そのaと”たがいに素”である数（ｂ）をプログラムで求めたいんです…。 ある本によると適当な二つの素数ｐ、ｑがあるとしてこのふたつの積（つまりｐ＊ｑ）をｍとします。また、(p-1)(q-1)＝aとすると ”gcd(b,a)≡1(mod m)” という式を満たすんだそうです…。 ※この中にでてくる値で実際に分からないのは"b"のみです。 ※ここで書いているgcd(b,a)というのはaとｂの最大公約数のことです。 --------------------------------------------------------------------- かなり難しいのでこの質問の回答をいただくと本当に助かります。 よろしくお願いしますm(_ _)m
- ベストアンサー
- Visual Basic
- 再帰関数とユークリッドの互除法を用いて最大公約数を求める
学校の課題で、再帰関数とユークリッドの互除法を用いて１０～１０００００までの最大公約数を求めるという問題が出て自分でプログラムを作ってみたのですが無限ループに入ったり、関数が使えてないみたいでできません。プログラムを見て頂いて、どこを改善したらいいかを教えてください。 #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); } です。期限が今日の夜までで、ぎりぎりなんですがよろしくお願いします。
- ベストアンサー
- C・C++・C#
- ユークリッドの互除法について
ユークリッドの互除法を使って最大公約数、整数解を求められると聞いたのですが、イマイチ要領がつかめません。 もしよろしければ、どなたかユークリッドの互除法での最大公約数、整数解の求め方を教えてください。
- 締切済み
- 数学・算数
- 最大公約数？？
今日のyahooニュースで厚生事務次官の事件で 見出しに"異例の警戒＝最大公約数で展開" や本文に警察当局の話として”今後も発生が懸念され、最大公約数で捜査と警戒を展開する必要がある”というのが載っていました。 このときの最大公約数とはどういう意味ですか。 yahoo辞書で調べたのですが、最大公約数には １ 《 greatest common measure 》二つ以上の自然数の公約数の中で最大のもの。 ２ 種々の意見の間にみられる共通点。「多くの発言の中から―を出す」 という２つの意味があり、今回の場合はまず１は違うのはすぐわかるのですが、２でもよく意味がわかりません。 単に"最大規模"の誤りでしょうか？ よろしくお願いします。
- ベストアンサー
- 日本語・現代文・国語
お礼
なるほど、そういうことだったんですね。 よくわかりました。ありがとうございます。