問一下輾轉相除法原理是什麼?
25235412 發表於 2014-11-7 14:17 
和這些判斷法其實是同一個原理
差別在判斷法是固定的倍數在刪，而輾轉相除法是不固定的倍數在刪
你用情境想好了
式子真的會讓你看不下去 .....
假設這裡有一堆十元硬幣(超過五百個)，你想知道這堆硬幣的數量是不是 6 的倍數，你怎麼做 ?
一個一個數 ? 太慢 .....
是我的話，先疊一個 12 枚十元的一疊，然後把其他錢疊成跟那疊差不多高度的
全疊完後，把所有的錢弄成和 12 枚十元那疊一樣高，完成後頂多剩一疊高度不足
那疊就是 a / 12 = ? ..... 的餘數
題目是問是不是 6 的倍數，但不用緊張，因為 12 是 6 的倍數，所以關鍵就在高度不足的那疊
如果"剩餘"那疊數量是 0 或 6 (的倍數)，那這整堆硬幣數量就是 6 的倍數 .... (0表示剛好疊完)
結果，剩餘的9枚，那不是 6 的倍數
這時，題目又突然改問了 (這出題目的很奸詐)
那這整堆硬幣，是不是3的倍數呢 ?
聽完，真該笑了，6 是 3 的倍數，被疊好 12 枚的那堆錢一樣不用管他
"剩餘"那疊數量，再看是不是 3 的倍數就行了，9 是 3 的倍數，那是了
這裡有兩個重點 .....
1. 排好的不用管，因為那些都會是 ok 的
2. 餘數可以繼續往下追 .....
輾轉相除法也是一樣
a > b ，m = a , b 的最大公因數，求 m = ?
第一步 a = bc + d
d = 0 ，結束 b 是最大公因數
d ≠ 0 ， bc 不用管了，因為 b 是 m 的倍數，bc 不會影響結果。 d 可以繼續往下追 ....
從代數來看， a , b 都是 m 的倍數， d = a - bc = m(① - ②c) 也一樣會是 m 的倍數
所以 m = a, b 的最大公因數 = b, d 的最大公因數，而且 b > d
第二步 ... 一樣的再玩一次
b = de + f
f = 0 ，結束 d 是最大公因數
f ≠ 0 ， de 不用管了，因為 d 是 m 的倍數，de 不會影響結果。 f 可以繼續往下追 ....
所以 m = a, b 的最大公因數 = b, d 的最大公因數 = d, f 的最大公因數，而且 d > f
..... 重複可以愈找愈小，最後可以找到有 = 的時候，然後最大公因數就找到了 .... |
