- ベストアンサー
最大公約数の証明
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
aとbに１以外の共通の約数がはいっていないとき、 gcd(a,b)=d=１となって a^2とb^2にも共通の約数はないので、 gcd(a^2,b^2)=d^2=１ gcd(a,b)=dなので a=a'×d b=b'×dと書ける。 （a'とb'には共通の約数がない。） a^2=a'^2×d^2 b^2=b'^2×d^2 するとa'とb'それぞれ２乗しても共通の約数はないので 最大公約数はd^2となります。
関連するQ&A
- 2^91-1と2^65-1の最大公約数
2^91-1と2^65-1の最大公約数を求めるにはどうすればいいのですか？ これほど大きな値だと共通の素数で割ることもユークリッドの互除法も使えそうにありません。 ちなみにコンピュータに解いてもらったら GCD(2^91-1,2^65-1)=8191 でした。
- ベストアンサー
- 数学・算数
- 最大公約数を求めたい！
二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか？？ ＜さらにもし出来る方がおられたら…＞------------------------------------ 実は最終的にはある数（a（素数））があって、そのaと”たがいに素”である数（ｂ）をプログラムで求めたいんです…。 ある本によると適当な二つの素数ｐ、ｑがあるとしてこのふたつの積（つまりｐ＊ｑ）をｍとします。また、(p-1)(q-1)＝aとすると ”gcd(b,a)≡1(mod m)” という式を満たすんだそうです…。 ※この中にでてくる値で実際に分からないのは"b"のみです。 ※ここで書いているgcd(b,a)というのはaとｂの最大公約数のことです。 --------------------------------------------------------------------- かなり難しいのでこの質問の回答をいただくと本当に助かります。 よろしくお願いしますm(_ _)m
- ベストアンサー
- Visual Basic
- 最大公約数、定理の証明
a,bを a=b=0 でない2つの整数とするとき a*r + b*s =(a,b) のような整数 r,s が存在する --------------------------------------- という定理があって、この定理を使って 次の定理を証明せよ、という問題なのですが… d=(a,b) 整数 n は、 n|d のとき、その時に限り a と b の公約数である … n|d は dはnで割り切れるという意味 どういうふうに導くのかわかりません。 d=(a,b)= a*r + b*s = t*n (tは整数) とおく、ここまで何となくやってみたのですが… 「公約数」であることを示す方法、目標が見えません。 教えてください。
- ベストアンサー
- 数学・算数
- a,bの最大公約数を求める関数をつくってみたのですが、aまたはbが零の
a,bの最大公約数を求める関数をつくってみたのですが、aまたはbが零の時の処理としては、どのようにするのが適当かがわかりません。ある数と零の最大公約数ってどうなるんでしょうか？ #include <iostream> using namespace std; // 整数 a, b の最大公約数を求める int gcd(int a, int b) { if(b == 0) return -1; // この戻り値は適当なのか？ int r = a % b; // aをbで割った余り if ( r == 0 ) return b; // 余りが0ならbが最大公約数である else return gcd(b,r); // 余りが0でなければbとrの最大公約数を返す } int main() { cout << "gcd(1000,100) = " << gcd(1000, 100) << endl; return 0; }
- 締切済み
- C・C++・C#
- 最大公約数について
「a,b,c,rが正の整数で、a=rb+cであるとき、a,bの最大公約数とb,cの最大公約数は一致することを証明せよ。」 という問題の解答の出だしが、 「aとbの最大公約数をm、bとcの最大公約数をnとおくと a=mA, b=mB（AとBは互いに素な整数） b=nB',c=nC（B'とCは互いに素な整数） と書ける」 となっているのですが、なぜこう書けるのかわかりません。 「a=mA, b=mB」「b=nB',c=nC」とかけるのはわかりますが、なぜAとB,B'とCが互いに素と言えるのかわかりません。 思いつく反例を上げると、a,b,cは異なる数とは問題文に書かれていないので、もしaとbが同じ数だとしたらA=Bとなり互いに素ではありませんよね？
- ベストアンサー
- 数学・算数
- 3次式と2次式の最大公約数の問題
・Xの3次式「X3乗＋2X2乗－X－2」とXの2次式「3X2乗＋a2乗X－2a」の最大公約数が「X＋1」であるとき、aの値を求めよ。 こちらの問題の答えは「１」とあるのですが、答えだけで解き方が載っていないので、求め方がわかりません。どなたか分かる方はいますでしょうか。 そもそも、「式と式の最大公約数」というものがどういうものなのかがつかめていません。最近、参考書で「式と式は割ることができる」ということを学習したばかりなのですが、最大公約数というとどういうことなのかが良くわかりません。それと、最大公約数があるということは、式と式にも最小公倍数もあるということでしょうか。 また、「式と式の最大公約数」というのはどの範囲(例えば数I、数Bなど)で出てくるものなのでしょうか。 質問の数が多くなってしまいましたが、分かる方がいましたら教えていただきたいです。
- ベストアンサー
- 数学・算数
お礼
簡潔でわかりやすい説明をありがとうございます！！ とても参考になりました。