→ penguin7272 :好像就只是翻譯.. 08/22 11:48
推 testishard :gcd(a,b)=d=0??還有a,b都是0的話是要怎麼取gcd啊？ 08/22 13:13
設d是gcd(a,b)
以下證明對於所以非負整數a,b都有整數x,y使ax+by=d
使用數學歸納法
令n=a+b, 這裡對n歸納
n=0時表示a=b=d=0,取x=y=0則ax+by=d
假設n=0,1,...,k-1時都有x,y使ax+by=d
n=k時
由對稱性設a≧b
對於原命題考慮a-b和b兩數
兩數和為k-b
當b=0時d=0,取x=0即可
若b≠0,則k-b<k
由假設知存在兩數x,y
使(a-b)x+by=d
整理即ax+b(x+y)=d
滿足題意
由數學歸納法知原題成立
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.71.200.27