- ベストアンサー
最大公約数 証明
整数(環？)についての証明がわからないので質問します。 証明することは、 p,qを2整数(または数体Kにおけるxの整式)とし、式 pu+qv・・・(1)においてu及びvを整数(Kにおける整式)全体にわたって変ずるものとする。かくして得る整数(整式)の中の最小正の整数(xについての最低次の整式)をdとし、d=pu0+qv0・・・（2）とする。然るときdはp,qの最大公約数である。 です。証明は以下のように書いてあります。 実際d'がp,qの公約数ならば、(2)からd'はdの約数である。他方dはu,vのいかんを問わず常に(1)を割り切っている。何となれば(1)をdで除した剰余をr(rは０に等しくない) とすれば、 pu+qv=ad+r=a(pu0+qv0)+r つまりp(u-au0)+q(v-av0)=r ところでｒはdより小なる正整数(dより低次の整式)であるから、上の関係はdが(1)が最小(最低次)であるという仮定に矛盾する。故にu,vのいかんを問わずdは(1)を整除する。今u=1,v=0とおけば(1)はpとなり,u=0,v=1とおけば(1)はqとなるから,dはpをもqをも割り切る。それゆえdはp,qの最大公約数である。 自分は、2*1+3*2＝8などから、8は2と3の最大公約数ではないと思い。何かp,u,q,v に条件があるのではと考えましたが、整数という条件しか探せませんでした。 剰余をｒとした後の計算と、剰余ｒを仮定すると矛盾するからｒ＝0ということ、ぐらいしかわかりません。ヒントでもよいので教えてくださいお願いします。
- situmonn9876
- お礼率91% (646/703)
- 数学・算数
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
良く読みましょう。 取り敢えず有理整数環で考えます。今、p=2, q=3とした時、上のdは、pu+qv = 2u + 3v （ただし、u, vは『整数全体を動く』）の形で書けるものの『中で最小の正の数』とするのですよ（と書いてありますよね？） 繰り返しますが、u, vは「すべての整数の組み合わせ」を考え、そのなかで2u + 3v が正の整数となるもののなかから、「最小のものを取ってくる」のです。2u + 3v（但しu, vは整数）の形で書けるもののなかで、8より小さい正の整数はまだあるでしょう？ 一度考えて、分からない事があれば、補足に下さい。
関連するQ&A
- cはpとqの公約数で、dを最大公約数とします。
cはpとqの公約数で、dを最大公約数とします。 ここで、最大公約数となる条件として 1)dで2つの整数pとqが割り切れる。 2)pとqのどんな公約数cでもdを割り切ることができる。 この関係を使って、c=p∧qで表すとします 例)p=18 q=12 とすると 18=1*2*3*3 12=1*2*2*3なので 公約数cは二つの共通部分 1 と 2(1*2より) と 3(1*3より) と 6(2*3より) となる ここで質問ですが、最大公約数dは d=max c つまりd=max{p∧q}で表すことはできますか？ できれば証明をお願いしたいです＞＜ 表すことができなければ、 p∧qを使って他に表す方法があれば教えてください。
- 締切済み
- 数学・算数
- 最大公約数、定理の証明
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は整数) とおく、ここまで何となくやってみたのですが… 「公約数」であることを示す方法、目標が見えません。 教えてください。
- ベストアンサー
- 数学・算数
- 最大公約数を見つけたい
C++初心者です。Visual studio 2005を用いてvisual C++の計算フォームアプリケーションを作りたいのです。 ２ヶ所のテキストボックスに整数を入力させ、「実行」ボタンを押すとその２つの整数の最大公約数を出力させたいのですが、どうも上手くいきません。 できるだけ簡素なコードで最大公約数を見つけるにはどうすればいいでしょうか？ どうかよろしくお願いいたします。
- ベストアンサー
- 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となり互いに素ではありませんよね？
- ベストアンサー
- 数学・算数
- 最大公約数を求めたい！
二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか？？ ＜さらにもし出来る方がおられたら…＞------------------------------------ 実は最終的にはある数（a（素数））があって、そのaと”たがいに素”である数（ｂ）をプログラムで求めたいんです…。 ある本によると適当な二つの素数ｐ、ｑがあるとしてこのふたつの積（つまりｐ＊ｑ）をｍとします。また、(p-1)(q-1)＝aとすると ”gcd(b,a)≡1(mod m)” という式を満たすんだそうです…。 ※この中にでてくる値で実際に分からないのは"b"のみです。 ※ここで書いているgcd(b,a)というのはaとｂの最大公約数のことです。 --------------------------------------------------------------------- かなり難しいのでこの質問の回答をいただくと本当に助かります。 よろしくお願いしますm(_ _)m
- ベストアンサー
- Visual Basic
お礼
お返事ありがとうございます。 2*(-1)+3*1=1などは気付けました。具体的な数入れて、しっかりと証明を読むようにします。