什么是歐幾里得算法?

學(xué)過(guò)算法或者程序設(shè)計(jì)遞歸實(shí)現(xiàn)的時(shí)候, 我們會(huì)經(jīng)常會(huì)看到求解最大公約數(shù)的例子, 今天我們就介紹并證明求解公約數(shù)的方法: 輾轉(zhuǎn)相除法： 又名歐幾里德算法（Euclidean algorithm)。

我們先分析一下這個(gè)算法的大概流程: 假如a = 25, b = 10

第一次運(yùn)行時(shí)gcd(25, 10) 我們會(huì)返回gcd(10, 25 % 10)也就是gcd(10, 5)

于是程序開(kāi)始遞歸, 因?yàn)榇藭r(shí) b 不為0, 所有第二次返回的是gcd(5, 10 % 5)也就是gcd(5, 0)

此時(shí)的參數(shù) b 已經(jīng)為 0 了， 結(jié)果直接返回 a 也就是 5, 所以 25 和 10 的最大公約數(shù)是 5

那么, 想要證明歐幾里得算法實(shí)際只要證明 gcd=(a,b) = gcd(b,a%b) 就可以了， 也就是說(shuō)如果 c 是 a 和 b 的最大公約數(shù), 那么 c 也是 b 和 a % b 的最大公約數(shù)

命題

歐幾里得算法最先提出的命題如下:

設(shè) n 是一個(gè)自然數(shù)，q 表示一個(gè)正自然數(shù)，那么存在自然數(shù) m 和 r 使得 0 <= r < q 并且 n = m*q + r

在證明這個(gè)命題前, 我們先要知道關(guān)于自然數(shù)的一個(gè)性質(zhì):

假設(shè) a, b 為任意自然數(shù), 那么 a < b 當(dāng)且僅當(dāng) a + 1 <= b?

知道這一性質(zhì)后我們就可以通過(guò)數(shù)學(xué)歸納法證明歐幾里得算法了:

順便提一下， 正因這個(gè)算法標(biāo)志著數(shù)論的開(kāi)始，至于數(shù)論是什么?? 可以打個(gè)比方, 密碼學(xué)rsa(非對(duì)稱加密)等算法的設(shè)計(jì)就是個(gè)數(shù)論問(wèn)題

繼續(xù)證明輾轉(zhuǎn)相除法

回到正題, 現(xiàn)在我們知道自然數(shù)都可以表示為 n = m*q + r 的形式， 聰明的你會(huì)發(fā)現(xiàn)這條式子的意義: 當(dāng)用一個(gè)正自然數(shù)去除一個(gè)自然數(shù) n 的時(shí)候, m 為商, r 就是余數(shù)， 也就是(n % m)

假設(shè) a 是n, m 的公約數(shù)，也就是 n, m 能被 a 整除

接下來(lái)我們只需要證明 r 也能被 a 整除

下面我們對(duì)其變形:

r = n - m*q

同時(shí)除 a 得:

r / a = n / a - (m*q) / a

由于 a 是n, m 的公約數(shù), 所以 n / a 是整數(shù), (m * q) / a 也是整數(shù), 那么兩個(gè)整數(shù)相減得到的還是一個(gè)整數(shù) r / a

于是我們就證明了 r 也能被 a 整除, 這就是為什么說(shuō) a,b 和 b,a%b 的最大公約數(shù)相等了!

收獲與感想

在學(xué)習(xí)歐幾里得算法的時(shí)候搜索了大部分的證法, 他們第一步直接假設(shè) n = m*q + r , 并沒(méi)有給出"自然數(shù)都可以表示為 n = m*q + r 的形式"的證明。。。

證明的方法來(lái)自于<<陶哲軒實(shí)分析>>中介紹的數(shù)學(xué)歸納法，這真是個(gè)證明命題的好方法, 只要假設(shè)性質(zhì) P(n) 成立, 那么只要證明性質(zhì) P(n++) 就可以了, 實(shí)際上像自然數(shù)系，整數(shù)等數(shù)系的定義都是通過(guò)類似的遞歸定義得到的,? 真是太奇妙了!!!?