辗转相除法 算法（辗转相除法例子）
•
2024-06-17 06:30:44
摘要 大家好,飞飞今天来为大家解答以下的问题，关于辗转相除法 算法，辗转相除法例子这个很多人还不知道,那么下面让我带着大家一起来看看吧！1...
大家好,飞飞今天来为大家解答以下的问题，关于辗转相除法 算法，辗转相除法例子这个很多人还不知道,那么下面让我带着大家一起来看看吧！
1、辗转相除法最大的用途就是用来求两个数的最大公约数。
2、 用（a,b）来表示a和b的最大公约数。
3、有定理： 已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。
4、例：求 15750 与27216的最大公约数。
5、 解： ∵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。
本文分享完毕，希望对大家有所帮助哦。
版权声明：本文由用户上传，如有侵权请联系删除！
标签：
辗转相除法例子