求兩個正整數最大公約數

一、“更相減損之術”來歷

《九章算術》是中國古代的數學專著，其中的“更相減損術”可以用來求兩個數的最大公約數，即\"可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。\"

翻譯成現代語言如下：

第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用2約簡；若不是則執行第二步。

第二步：以較大的數減較小的數，接著把所得的差與較小的數比較，并以大數減小數。繼續這個操作，直到所得的減數和差相等為止。則第一步中約掉的若干個2與第二步中等數的乘積就是所求的最大公約數。

其中所說的\"等數\"，就是最大公約數。求\"等數\"的辦法是\"更相減損\"法。第一步\"可半者半之\"是指分子分母皆為偶數的時候，首先用2約簡。加入這一步的原因可能是，分母、分子皆為偶數是在分數加減運算的結果中比較容易遇到的一種情況，用這種方法有可能減少數字的位數，簡化計算。當然，省略這個以2約簡的步驟，也能得到正確的答案。

二、“更相減損之術”理論

理論依據：兩個正整數： 可知 與 有相同的約數，即兩個整數的最大公約數等于其中較小的數和兩數之差的最大公約數，繼續這樣的運算，不斷縮小兩數，直到產生一對相等的數，這就是最大公約數。

三、“更相減損之術”算法表示與程序框圖