使用者23896760229092021-03-01 21:29:35

最大公約數：指兩個或多個整數共有約數中最大的一個。

原理如下：

假設有兩個數x和y，存在一個最大公約數z=（x，y），即x和y都有公因數z， 那麼x一定能被z整除，y也一定能被z整除，所以x和y的線性組合mx±ny也一定能被z整除。（m和n可取任意整數）對於輾轉相除法來說，思路就是：若x>y，設x/y=n餘c，則x能表示成x=ny+c的形式，將ny移到左邊就是x-ny=c，由於一般形式的mx±ny能被z整除，所以等號左邊的x-ny（作為mx±ny的一個特例）就能被z整除，即x除y的餘數c也能被z整除。

由以上的推理可知 a / b的餘數 也能被 （a，b）的最大公約數整除，因此就將問題轉化為求 其中較小的數和餘數的最大公約數，最終將範圍不斷減小，從而求出答案。