最大公約数、定理の証明

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は整数)
とおく、ここまで何となくやってみたのですが…
「公約数」であることを示す方法、目標が見えません。

教えてください。

No.2 ベストアンサー 回答者： takebe 回答日時： 2001/07/24 20:00

n|d ⇒ 公約数 を示すのは簡単ですよ．∃r,s a*r + b*s = dは使わなくてもできますね．

dはaの約数なので，

a = p * d = p * q * n

などと表せ，nがaの約数であることがわかります．bについても同様ですね．

公約数 ⇒ n|d を示すのは，a*r + b*s = dを使うとできるようです．

この回答へのお礼

この回答をもらって、しばらく悩んでいました。
両方向から、攻めればいいんですね。

公約数→n|d　にかなり悩まされましたけど、
解けてみればなんてことない…でも、すっきりして面白いですね。

とても参考になりました、ありがとうございました。

お礼日時：2001/07/24 22:30

No.1 回答者： taropoo 回答日時： 2001/07/24 19:33

(a,b)の定義がないので定理と言われても何を主張した定理なのか分かりませんが、文脈から察するにa=2, b=3に対して12が

　　　　12 = 2*3 + 3*2
のようにa*r + b*sの形に表せるような整数r, sが存在するとき、
　　　　12 = (2,3)
と表すと言う事でしょうか？
それにしても左辺は一つの数を表していますが右辺は数の性質を表していて、これを等号で結んでしまって良いのでしょうか？

しかし(a,b)の定義に関しては求められている証明にはあまり関係ないので置いておきましょう。
　　　　n|(a*r + b*s) ⇔ n|a かつ n|b
を証明すれば良いんですよね？しかし証明は出来ません。なぜなら反例があるからです。
a=2, b=3, r=2, s=1, n=7 とおくと
　　　　n|(a*r + b*s) ⇔ 7|7 ⇔ true
ですが
　　　　n|a ⇔ 7|2 ⇔ false
　　　　n|b ⇔ 7|3 ⇔ false
です。

何か問題を読み違えていらっしゃいませんか？

この回答への補足

すみません、何の前置きもなく書いてしまいました。

(a,b) というのは、aとbの最大公約数です。
ものによっては　gcd(a,b)とも書いてあります。

補足日時：2001/07/24 19:57