如何證明輾轉相除法(歐幾里德演算法)？
大家好，我在codewars上遇到一個題目，其核心是要求n個數的最小公倍數。最小公倍數從前我是筆算幾次就可以出來結果了。但是要寫成python演算法就不太懂了。百度了一下，知道最小公倍數可以通過求最大公約數求出，最大公約數可以根據歐幾里德演算法求出。
但是我對百度到的歐幾里德演算法證明最後的一句不是很理解：（a,b）和（b,a mod b）的公約數是一樣的，為什麼其最大公約數也必然相等？以下是我找到的證明過程。定理：兩個整數的最大公約數等於其中較小的那個數和兩數的相除餘數的最大公約數。最大公約數（greatest common divisor）縮寫為gcd。證明：gcd(a,b) = gcd(b,a mod b) (不妨設a&>b 且r=a mod b ,r不為0) a可以表示成a = kb + r（a，b，k，r皆為正整數），則r = a mod b假設d是a,b的一個公約數，記作d|a,d|b，即a和b都可以被d整除。
而r = a - kb，兩邊同時除以d，r/d=a/d-kb/d=m，等式左邊可知m為整數，因此d|r因此d也是（b,a mod b）的公約數因此（a,b）和（b,a mod b）的公約數是一樣的，其最大公約數也必然相等，得證。
證明可能沒有說清楚，不便於理解。他假設一個數d，是兩個數的公約數(如果兩個數都屬於正整數，必然存在一個正整數同時是這兩個數的約數，如果加上負整數，會至少有兩個不為零的整數，負整數這塊我不太確定)，也就是說，分別同時是兩個數的約數，由乘法的分配律可以證明出d也是餘數的約數。這一步很好理解吧。再看d，當d取任何其只要滿足同時是這兩個數的約數的時候，結論都成立，也就是說d可以取兩個數的任意公約數，當然也能取最大公約數，因為最大公約數也包含在公約數集裡面。所以d可以讓代表兩個數的任意公約數。不知道這樣說你有沒有理解。
還有一種是遞歸的思維求證，我管它叫遞歸二分思維，(這裡的名字是我自己賦予的定義，在數軸上兩個不相等的數之間取中點，叫對稱二分，取兩個數之間的任意數，叫做二分， 和我們常常規說的二分演算法裡面的二分有點區別，因為對稱二分也包含在內。)不過主要目的是求證歐幾里得演算法的思維，而不是結果的正確，更多是對歐幾里得演算法的一些數學意義上的解釋。他這裡沒說清楚，其實是說d是a,b的任意一個公因數，d也是b，r的任意公因數。也就是a,b的任意一個公因數也必然是b,r的任意一個公因數，a,b的公因數集等於b,r的公因數集。那麼這兩個集合里的最大值肯定也是相等的。舉個例子來說，我們求gcd（12，18）
- 12，18的公因數有：1，2，3，6。
- 由演算法gcd（a，b）=gcd(b,a%b)有gcd（12，18）=gcd(18,12%18)=gcd(18,12)
- 18,12的公因數有：1，2，3，6。
- 接著往下算，gcd（18，12）=gcd(12,18%12)=gcd(12,6)
- 12,6的公因數有：1，2，3，6。
- 再往下，gcd（12，6）=gcd(6,12%6)=gcd(6,0)
- 0,6的公因數有：1，2，3，6。
- 最後，就由gcd（0，n)=n得gcd（0，6）=6
你看，第1，3，5，7他們的公因數集都是相等的，自然的，集合里的最大值也是相等的。
我的證明是這樣的：
證明：也就是證明如果a=bq+r，那麼d是a和b的公因數，當且僅當d是b和r的公因數。
1)設d是a和b的公因數，則d|a且d|b，於是d|(a?bq)。也就是說d|r,
因為r=a?bq.
==》d是b,r的公因數。
這裡解釋一下d|（a-bq)：
因為d|a，d|b,所以有a=dx,b=dy;把d代入a-bq有dx-dyq=d(x-yq).
所以d|（a-bq)
2)設d是b和r的公因數，則d|r且d|b。於是，d|（bq+r）.所以d|a
==》所以d是a,b的公因數。
綜上，a,b的所有公因數和b,r的所有公因數是一樣的。那麼，d是a，b的最大公因數，當且僅當d是b和r的最大公因數。
gcd(a+b,b) = gcd(a,b)是很顯然的，因為若d同時是a和b的約數，d也一定是a+b和a+b的約數既然gcd(a+b,b)=gcd(a,b)，取模也是一樣的，就當多減幾次。
感謝@OmerJ和題主的評論啟發
設想兩個線段a,b表示整數，刻度為一。這樣，對於較長的線段a可以看成較短的線段b,再加上長出來的一段c。那麼，如果一個數是a的因子也是b的因子，那麼，可以轉化成，必然也是c的因子。因為，對於長線段來說，他是由跟b一樣長的部分和多出來的部分組成的。多出來的部分必然和b有相同的因子。其實可以看成，短的部分c保留了原長線段a的性質。從公因子的集合來說。
最終轉化成任意正整數和0的最大因子。對於0，來說，可以分解出任意多的因子。對於其它正整數來說，最大的因子就是其自身。所以，一旦形成一方位零，就可以斷定，輾轉相除剩下來的正整數就是原問題的最大公因子。關鍵在於轉化保持性質不變。
轉化性質怎麼保留的呢？想一下因式分解，1,2,3,5,7,....比如，10,和30。輾轉相除，30會變成0,而0保留了所有因子。
10繼續保留其自身性質。感謝證明！聽說整數很大時輾轉相除法里的取模運算性能較低，所以針對這個問題我來分享一個較優解吧：移位運算 + 更相減損術
知識基礎：二進位轉化，python位運算符。直接上圖：
剛看夢見的倉鼠漫畫學會的，他是用C寫的，我把這個思路遷移到了Python~//w//
作者：kylinxianga可以表示成a = kb + r（a，b，k，r皆為正整數，且r&
如果，要求a和b的最大公約數，設為c，a=m*c，b=n*c，m和n是的最大公約數是1。否則，c就不是a和b的最大公約數。
剩下的問題，就是m和n輾轉相除之後，結果是1的證明了。它的逆否命題，比較好證明。
推薦閱讀：
※《古今數學思想》這本書為什麼唯獨沒有對中國數學的描述？
※如何看待三江方士這個人？
※預篇：伯爵Fagnano與Euler的加法定理(I)