證明

引用：

寫道:
證明：輾轉相除法為何可以求出最大公因數

2└12 60
6 ---------
└6 30
--------
└1 5
------
2.6.12

應該是吧!

你可以先假設A＞B
且(A,B)=x, A=ax, B=bx

第一次
A-Bn=(a-bn)x
(n是使Bn最靠近A的自然數 n=[A/B])
在假設C = cx= (a-bn)x

第二次
B-Cn=(b-cn)x
(n是使Cn最靠近B的自然數 n=[B/C])
如果在這次中B-Cn=0則代表說c=1
則C就是A,B的最大公因數了

如果不是零 反覆做下去就是了
每次相除之後的餘數都會有最大公因數
所以才會如此

例如說
A=55=11*5
B=20=4*5

A-Bn=55-20*2=3*5
C=cx=3*5

B-Cn=20-15*1=1*5
D=dx=1*5

C-Dn=15-5*3=0*5
∵C-Dn=0
∴D=(a,b)= x =5

用輾轉相除法表示就是==>
　｜55｜20｜
２｜40｜15｜１
　├－┼－┤
　｜15｜ 5｜
３｜15｜　｜
　├－┤　 ｜
　｜0 ｜　｜
所以(55,20)=5

你可以去看看今年高一的課本 雖然有些模糊地帶 但是多少有些幫助

引用：

kurismis117 寫道:

引用：

寫道:
證明：輾轉相除法為何可以求出最大公因數

2└12 60
6 ---------
└6 30
--------
└1 5
------
2.6.12

這好像不是輾轉相除法吧

兩數a,b
設(a,b)=m,a=hm,b=km
a=bq+r,(q,r屬於N)
m│a, m│b
r=a-bq=m(h-qk)
所以r│m
(a,b)=(b,r)=m
輾轉相除法原理大致上就是這樣
最後可得到m

引用：

1123581321 寫道:
看不懂，第一個人的（P.S這題是我發的）

那你幹嘛部用帳號ㄚ?

David的說法好像有點倒果為因ㄟ~~基本上，我覺得高一課本寫的不模糊，有點數學基礎的人就可以看懂了，如果真的不懂，就把卡住的地方提出來，大家比較容易幫你的忙唷~~

不過我相信你，課本再多看幾眼應該就ok了!

利用線性組合便可。