最大公因數gcd

Question

證明對任何正整數a 和b，存在整數r 和s 使得a 和b 的最大公因數gcd(a,b)可寫成ar＋bs

coolyes,你證明得非常好，我再贊助2點，可否證明
如果(x,y) = 1→存在整數p、q
使得px＋qy = 1
謝謝

Answer 1

假設S={ax＋by｜ax＋by＞0，x,y是整數}
a^2＋b^2會屬於S，S≠空集合

所以S中必存在一個最小元素d，使得d=ar＋bs，其中r,s是整數
底下將證明 d=(a,b)


(1)
由除法原理，假設a=dg＋r，0≦r＜d
若r≠0，則r=a-dg=a-(ar＋bs)g=a(1-r)＋b(-sg)會屬於S
此與d是S中的最小元素不合
所以r=0，而有a=dg =>d｜a，同理可證得d｜b
故d|(a,b)=>d≦(a,b)

(2)
若m是(a,b)的任何一個公因數，設a=mh，b=mk
所以d=ar＋bs=m(hr＋ks)=>m｜d
故(a,b)|d => (a,b)≦d

綜合以上，若a,b是整數，則存在整數r,s，使得 ar＋bs=(a,b)

2007-03-12 18:31:13 補充：
≦是"小於等於"

Answer 2

兩位都證明得很好=_=

Answer 3

可以接受這個嗎？
如果(x,y) = 1→存在整數p、q
使得px＋qy = 1
可以的話，就假設(a,b) = k
→存在x、y：a = xk，b = yk；且(x,y) = 1
所以存在r、s
→rx＋sy = 1
→rkx＋sky = k
→ar＋bs = k



2007-03-13 10:59:18 補充：
証法與另一位大大類似
令A={px＋qy│x=px＋qy>0}，p,q為整數，
因為p=q=1時成立，此集合顯然不是空集合。
令d為此集合中之最小者，若d=1，則本定理得證。
若px＋qy=d>1，則任取A中一數：p'x+q'y，
以d除p'x+q'y，則得：
p'x＋q'y=ad＋r=apx＋aqy＋r,0<=r<d
→r=(p'-ap)x＋(q'-aq)y
→r=0或屬於A(不合，r<d)
所以d為A中任一數之因數
因為x,y均屬於A，所以d為x,y之公因數
但是(x,y)=1→d=1
證明完畢

2007-03-13 11:01:17 補充：
証法與另一位大大類似
令A={px＋qy│x=px＋qy>0}，p,q為整數，
因為p=q=1時成立，此集合顯然不是空集合。
令d為此集合中之最小者，若d=1，則本定理得證。
若px＋qy=d＞1，則任取A中一數：p1x＋q1y，
以d除p1x+q1y，則得：
p1x＋q1y=ad＋r=apx＋aqy＋r,0＜＝r＜d
→r=(p1-ap)x＋(q1-aq)y
→r=0或屬於A(不合，r＜d)
所以d為A中任一數之因數
因為x,y均屬於A，所以d為x,y之公因數
但是(x,y)=1→d=1
證明完畢