最近回顧之前寫的 RSA 算法相關的文章時，因為 RSA 跟質數有關，突然聯想到歐幾裡德求任意兩個自然數最大公約數的方法（又叫輾轉相除法）：拿 較小數 n 去除 較大數 m，如果 m 正好被整除，則 n 理所當然是最大公約數；而如果不能被整除，則得到一個 餘數 r，這個時候則把 r 當成較小數，n 當成較大數，再走一次上面的流程……總之，到最後一定會得到一個 餘數 或者說 較小數 r’ 能整除較大數，較小數 r’ 就是一開始 m 和 n 兩個數的最大公約數。

如果用 f(x, y) 來表示獲取 x 和 y 兩個正整數的最大公約數的函數，用 x mod y 來表示 x 除以 y 取餘數的操作，那麼上述歐幾裡德求最大公約數公式也可以用公式表示為：

x 和 y 均為自然數，假設 r = x mod y： 當 r 不為 0 時 f(x, y) = f(y, r) 當 r 為 0 時 f(x, y) = y

因為最大公約數英文為 Greatest Common Divisor，所以上述的 f(x, y) 中的 f 又常常用最大公約數的縮寫 gcd 代替。

一開始我總覺得這個公式非常反直覺，想不通為什麼最大公約數會跟餘數有關系。經過證明，的确如此，但就算證明出來依然覺得反直覺（其實上學那會兒很多數學公式都會帶給我這種感覺……）。不過這裡我想運用一下我最近了解到的關于人腦的兩個知識點來解決這個問題：第一，人腦善于通過具體的例子歸納總結而不是反過來；第二，人腦善于用圖形來思考問題。

先假設有兩根線，一根長 51 厘米，一根長 187 厘米，我們的目的是為了找到一根線（必須是 1 厘米的整數倍），正好能丈量這兩根線。很顯然，一根 1 厘米的線一定是滿足這個需求的。問題是，用來丈量的線，最長可以到多長？

我們不妨先假設最長的線有 n 厘米，那 51 必須是 n 的整數倍，187 也必須是 n 的整數倍。另外，我們可以很容易通過把 187 厘米的線與 51 厘米的線對齊的方式，從 153 厘米的線上剪 51 厘米的線下來，剩下的 136 厘米很顯然也必須是 n 的整數倍。

我們再利用 51 厘米線再從 136 厘米的線上剪 51 厘米下來……如此反複又剪了2次，136 厘米的線還剩下 34 厘米。同樣，34 也必須是 n 的整數倍。其實上面的過程也可以描述為：如果有一個數 n，能整除 187 和 51，那 n 必須也能整除 187 除以 51 的餘數 34。

我們把上面的結論再歸納一下，把具體的長度去掉，可以這麼說：如果有一個自然數 n，能整除自然數 a 和 b，那 n 也必須能整除 a 除以 b 的餘數。

再回到上面的例子。既然 187，51，34 三個數都能被 n 整除，再結合剛才的歸納，那不管是 187 除以 34 的餘數也好，還是 51 除以 34 的餘數也好，也都必須得能被 n 整除。很容易算出來上面所說的兩個餘數都是 17，并且到這個地步，我們也一眼能看出 17 已經能整除 34 本身。

以下是正兒八經的證明：

假如有一個自然數 c，能整除另外兩個自然數 a 和 b，那必然存在兩個正整數 m 和 n，能讓： a = mc；b = nc； 另外，如果 a mod b 為 r，且 r > 0，那必有一個自然數 k，能讓： a = kb r； 将上式 a 和 b 替換為 mc 和 nc，得到： mc = knc r; 即 r = mc - knc = c(m - kn) 因為 m，k，n 都是自然數，m - kn 也必須是自然數，則 r 一定是 c 的整數倍。

雖然為了看起來正規一點，還是寫了代數證明，但我還是覺得，公式、定義等一切抽象化的結果，其實都是人們對自己已經掌握的一種知識的精煉，但如果你隻是剛開始學，與其強行理解别人的結論，遠不如自己用具體的例子去歸納來得輕松和紮實，比如說網上都說要不斷用兩個數裡較小的數去除以餘數來獲取最大公約數，但通過上面的例子可以看出并不一定非要用較小的數來除以餘數。

要注意的是，上面的證明過程隻證明了兩個數它們任意一個公約數都是這兩個數相除的餘數的約數，但歐幾裡德法求出來的數一定是最大的那個公約數嗎？這可也是需要證明的：

我們先假設歐幾裡德法最後得到的最小可能餘數，也就是某個約數，為 c，實際的最大公約數為 g，因為 c 肯定能整除最大公約數 g，所以 c ≤ g；

而我們通過之前的證明，可以得到通過輾轉相除，無論是哪一步産生的餘數，都能被原兩個數任意一個公約數整除，其中包括最大公約數 g，所以又會得到 c ≥ g；

綜上所述，c 隻能等于 g。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!