- ベストアンサー
2^91-1と2^65-1の最大公約数
stomachmanの回答
- stomachman
- ベストアンサー率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-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)>→ 終わり。 "="の左辺のカッコはずして展開すれば右辺になります。
関連するQ&A
- 最大公約数について
ユークリッドの互除法について勉強していて 途中で疑問に思ったことがあるのですが 例えば 288と108という数について 288と108の最大公倍数は36 288÷108=2余り72 ここから 108と72を取り出して この二つの数の最大公倍数も36 108÷72=1余り36 ここから72と36を取り出して、 この二つの数の最大公倍数も36 となりますが、なぜ割る数と余りの最大公倍数が、初めの数の最大公約数とずっと同じであり続けるのでしょうか? ユークリッドの互除法自体はある程度理解できています。 ユークリッドの互除法は、この数の動きを利用して最大公約数を求めていくようですが、なぜこのようなことになるのかが知りたいです。 難しい内容では理解できないので、できれば中学生レベルでも理解できるように説明してもらえればありがたいです。
- ベストアンサー
- 数学・算数
- 最大公約数から最小公倍数
ユークリッドの互除法についてなんですが、あるサイトでの公式?というか、 例》aとbの最大公約数を求めろ。 式がr(余り)=a-(a÷b)b それはわかったんです。 ですが、最大公約数から最小公倍数を出すという作業がわかりません。それと、手でやっているのでコンピューターは使っていません。 わかりやすく教えてください!
- ベストアンサー
- 数学・算数
- ユークリッド互除法の意義
2つの数の最大公約数の求め方の1つとしてユークリッド互除法を学習しました。 しかし、最大公約数の求め方は素因数分解でも求められます。 共通に割り切れるもので割っていけばよいので、わざわざユークリッド互除法を使わなくてもいいのでは?と思うのですが、ユークリッド互除法を使うことのよさってあるのですか? 回答よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 最大公約数を求めたい!
二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか?? <さらにもし出来る方がおられたら…>------------------------------------ 実は最終的にはある数(a(素数))があって、そのaと”たがいに素”である数(b)をプログラムで求めたいんです…。 ある本によると適当な二つの素数p、qがあるとしてこのふたつの積(つまりp*q)をmとします。また、(p-1)(q-1)=aとすると ”gcd(b,a)≡1(mod m)” という式を満たすんだそうです…。 ※この中にでてくる値で実際に分からないのは"b"のみです。 ※ここで書いているgcd(b,a)というのはaとbの最大公約数のことです。 --------------------------------------------------------------------- かなり難しいのでこの質問の回答をいただくと本当に助かります。 よろしくお願いしますm(_ _)m
- ベストアンサー
- Visual Basic
- 再帰関数とユークリッドの互除法を用いて最大公約数を求める
学校の課題で、再帰関数とユークリッドの互除法を用いて10~100000までの最大公約数を求めるという問題が出て自分でプログラムを作ってみたのですが無限ループに入ったり、関数が使えてないみたいでできません。プログラムを見て頂いて、どこを改善したらいいかを教えてください。 #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辞書で調べたのですが、最大公約数には 1 《 greatest common measure 》二つ以上の自然数の公約数の中で最大のもの。 2 種々の意見の間にみられる共通点。「多くの発言の中から―を出す」 という2つの意味があり、今回の場合はまず1は違うのはすぐわかるのですが、2でもよく意味がわかりません。 単に"最大規模"の誤りでしょうか? よろしくお願いします。
- ベストアンサー
- 日本語・現代文・国語
お礼
こんな方法があったんですか・・・知りませんでした。 いい勉強になりました。ありがとうございます。