求兩個(gè)正整數(shù)最大公約數(shù)

一、“更相減損之術(shù)”來歷

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

翻譯成現(xiàn)代語言如下：

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

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

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

二、“更相減損之術(shù)”理論

理論依據(jù)：兩個(gè)正整數(shù)： 可知 與 有相同的約數(shù)，即兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)之差的最大公約數(shù)，繼續(xù)這樣的運(yùn)算，不斷縮小兩數(shù)，直到產(chǎn)生一對(duì)相等的數(shù)，這就是最大公約數(shù)。

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