什么叫做辗转相除法？举几个例子

来源：百度知道编辑：UC知道时间：2024/05/26 19:27:30

辗转相除法最大的用途就是用来求两个数的最大公约数。

用（a,b）来表示a和b的最大公约数。有定理：已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。（证明过程请参考其它资料）

例：求 15750 与27216的最大公约数。

解：

∵27216=15750×1+11466 ∴（15750，27216）=（15750，11466）

∵15750=11466×1+4284 ∴（15750，11466）=(11466,4284)

∵11466=4284×2+2898 ∴(11466,4284)=（4284，2898）

∵4284=2898×1+1386 ∴（4284，2898）=（2898，1386）

∵2898=1386×2+126 ∴（2898，1386）=（1386，126）

∵1386=126×11 ∴（1386，126）=126

所以（15750，27216）=216

辗转相除法比较适合用来求两个比较大的数的最大公约数。