輾轉相除法---柳者

介紹：

輾轉相除法，也被稱為歐幾里德演算法。這是用來求兩個正整數最大公約數的演算法。是由古希臘數學家歐幾里德在其著作《The Elements》中最早描述了這種演算法，所以被命名為歐幾里德演算法。

計算：

1） 有a，b倆個整數（a>b）

2） r為a/b所得的商，且r1代表第一次得到的商，r2代表第二個得到的商，以此類推

3） q為a/b所得的餘數，且q1代表第一次得到的商，q2代表第二個得到的商，以此類推

4）

a/b = r1 …… q1

第一次

b/q1 = r2 …… q2

第二次

q1/q2 = r3 …… q3

第三次

5) ......

6)q(n)/q(n+1) = r(n+2) ...... 0 當餘數為0時，計算結束，a與b之間的最小公約數為q(n+1)

證明：

設a，b間的最大公倍數為W

因為a可以被W整除，b亦可以被W整除

設W*k（a） = a，W*k（b） = b

（ k（a）與k（b） 皆為正整數 ）

所以：

a-b = W*k（a） - W*k（b）

= W（ k（a）-k（b） ）

也就是說a與b的差可以被W整除（超超超超級重點）

所以（a-b）可以被W整除，

因為b與（a-b）都可以被W整除，

所以b-（a-b）可以被W整除

......

當（某個數減去某個數）/W 的餘數為0，

也就是說（某個數減去某個數） = W

那麼是怎麼化成下面的式子的呢：

a/b = r1 …… q1

第一次

b/q1 = r2 …… q2

第二次

q1/q2 = r3 …… q3

第三次

很好理解，因為上面的式子中：

餘數其實就是被除數-除數×商

因為除數是W的倍數，

所以除數×商也可以是W的倍數

所以被除數-除數×商也是W的倍數

也就是說餘數也是W的倍數

例子：

求1231與31的最大公約數：

1231/31 = 39……22

31/22 = 1 …… 9

22/9 = 2 ……4

9/4 = 2 …… 1

4/1 = 4 …… 0

說明：

所以1231與31的最大公約數為1