關於最大公因數...

Question

若(a,b)=d...
則必存在整數x、y，使得ax+by=d...
怎麼證明?!...

再次檢查一遍...
題目沒錯...-_-|||

Answer 1

設S= { ax+by | x,y屬於Z} , 存在最小的正整數元素ax1+by1設為d1
若( a , b ) = d , 很明顯 d 整除 d1……(1)
若 a ÷ d1 可表成 a = q1d1 + r1……(2)
　b ÷ d1可表成 b= q2 d1 + r2
　其中 0 <= r1,r2 < d1，r1,r2,q1,q2為非負整數
由(2)移項得 r1 = a - q1  d1 = a - q1  ( ax1 + by1 )
= a ( 1 - q1x1) + b ( -q1y1) 屬於S
若 r1 不為0，則 r1 < d1 與d1為最小矛盾 , ∴ r1 = 0，同理可證 r2 =0
故 d1 整除 a與b，得d1整除d ……(3)
由(1) 與 (3) 可知 d=d1，得ax1+by1=d，
亦即存在x1,y1使得ax+by=(a,b)

註：此定理有時會稱作最大公因數表現定理

Answer 2

題目有點怪怪的耶
應該是使ax+by=kd吧?
如果是醬子的話我會...
========================
因為(a,b)=d
令a=md
b=nd
所以ax+by=kd =>x*md+y*nd=kd
=> (x*m+y*n)*d=k*d
因為K為存在整數,又x,y為存在整數
所以 ax+by=kd 可得證