輾轉相除法, 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。它是已知最古老的演算法, 其可追溯至前300年。它首次出現於歐幾里德的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因子分解。
更相減損術,又稱"等值演算法"編纂於秦，書成於漢代。
“關於約分問題,實質是如何求分子,分母最大公約數的問題.<九章算術>中介紹了這個方法,叫做”更相減損術”,數學家劉徽對此法進行了明確的註解和說明,是一個實用的數學方法,中學生應該掌握它.
例1.今有九十一分之四十九,問約之得幾何?
我們用(91,49)表示91和49的最大公約數.按劉徽所說,分別列出分子,分母,”以少減多,更相減損,求其等也,以等數約之,等數約之,即除也,其所以相減者皆等數之重疊,故以等數約之.”列式如下:
91 49
1 49 42 1
42 7
5 35
7
這裡得到的7就叫做”等數”,91和49都是這等數的重疊(即倍數),故7為其公約數.而7和7的最大公約數就是7,(7,7)=7,所以 (91,49)=(42,7)=(7,7)=7
更相減損術在現代仍有理論意義和實用價值.吳文俊教授說:”在中國,求兩數最大公約數即等數,用更相減損之術,將兩數以小減大累減以得之,如求24與15的等數,其逐步減損如下表所示: (24,15)->(9,15)->(9,6)->(3,6)->(3,3)
每次所得兩數與前兩數有相同的等數,兩數之值逐步減少,因而到有限步後必然獲得相同的兩數,也即所求的等數,其理由不證自明.
這個寓理於算不證自明的方法,是完全構造性與機械化的儘可以據此編成程式上機實施”.吳先生的話不僅說明了此法的理論價值,而且指明學習和研究的方向.
更相減損法很有研究價值,它奠定了中國漸近分數,不定分析,同餘式論和大衍求一術的理論基礎.望能仔細品味
秦九韶是南宋數學家，關於秦九韶演算法，直到今天，這種演算法仍是多項式求值比較先進的演算法
輾轉相除法, 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。它是已知最古老的演算法, 其可追溯至前300年。它首次出現於歐幾里德的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。它並不需要把二數作質因子分解。
更相減損術,又稱"等值演算法"編纂於秦，書成於漢代。
“關於約分問題,實質是如何求分子,分母最大公約數的問題.<九章算術>中介紹了這個方法,叫做”更相減損術”,數學家劉徽對此法進行了明確的註解和說明,是一個實用的數學方法,中學生應該掌握它.
例1.今有九十一分之四十九,問約之得幾何?
我們用(91,49)表示91和49的最大公約數.按劉徽所說,分別列出分子,分母,”以少減多,更相減損,求其等也,以等數約之,等數約之,即除也,其所以相減者皆等數之重疊,故以等數約之.”列式如下:
91 49
1 49 42 1
42 7
5 35
7
這裡得到的7就叫做”等數”,91和49都是這等數的重疊(即倍數),故7為其公約數.而7和7的最大公約數就是7,(7,7)=7,所以 (91,49)=(42,7)=(7,7)=7
更相減損術在現代仍有理論意義和實用價值.吳文俊教授說:”在中國,求兩數最大公約數即等數,用更相減損之術,將兩數以小減大累減以得之,如求24與15的等數,其逐步減損如下表所示: (24,15)->(9,15)->(9,6)->(3,6)->(3,3)
每次所得兩數與前兩數有相同的等數,兩數之值逐步減少,因而到有限步後必然獲得相同的兩數,也即所求的等數,其理由不證自明.
這個寓理於算不證自明的方法,是完全構造性與機械化的儘可以據此編成程式上機實施”.吳先生的話不僅說明了此法的理論價值,而且指明學習和研究的方向.
更相減損法很有研究價值,它奠定了中國漸近分數,不定分析,同餘式論和大衍求一術的理論基礎.望能仔細品味
秦九韶是南宋數學家，關於秦九韶演算法，直到今天，這種演算法仍是多項式求值比較先進的演算法