辗转相除法

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

2、用（a,b）来表示a和b的最大公约数。

3、有定理： 已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。

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

5、解：

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

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

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

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

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

11、∵1386=126×11 ∴（1386，126）=126 所以（15750，27216）=216

【#辗转相除法#】到此分享完毕，希望对大家有所帮助。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！