辗转相除求最大公约数1 .算法证明2.Python算法
能被两个整数整除的最大整数称为两个整数最大公约数（Greatest CommonDivisor：gcd）。 求最大公约数的方法有很多，其中辗转相除法就是其中之一，是已知最古老的算法。
那个算法步骤是
1 .除以小数的数如果能被整除，小数就是求出的最大公约数
2 .无法整除时，用前面步骤的除数除以前面步骤的馀数，如果得到的馀数为0，则为该步骤的除数求出的最大公约数
3.2中得到的馀数如果不是0，则重复2直到得到的馀数为0，即公式可以被整除。 此时，成为除数数是求出的最大公约数
实际上，将求gcd(a,b)不断转化成求gcd(b,a%b)的问题()表示模具。 例如，如果有整数a，b，a%b=c，b%c=d，d%e=0，则gcd(a，b )=e。
那么为什么可以这样转换呢？ 以下请看相关证明。
1 .算法证明了欧氏辗转相除算法。 两个整数的最大公约数等于其中较小的数和两个数的相除馀数的最大公约数。
如果http://www.Sina.com/:ab，r=a%b (即除以两个数的馀数)，则a=bq r。
假设证明，则a和b都可以被d整除，可以表示为d|a，d|b。 r/d=(a-bq )/d=a/d-b/d*q=整数1-整数2 *整数3=整数，即剩余r也能被d整除，d|r。 据此，d是a,b的任一公因数
类似地，假设d是b,r的公因数，b和r可以被d整除，并可以表示为d|b，d|r。 a/d=(bqr )/d=b/d*q r/d=整数1 *整数2整数3=整数，即被除数a也能被d整除，d|a。 据此，d是b,r的任一公因数
综上所述，d是a,b的公因数，因此最大公约数也相等。
2.Python算法#输入整数a=int (输入(请输入第一个整数() ) (b=input ) )输入第二个整数) ) b为小数ifab : smalleb
是否要输入Created with Raphal 2.2.0整数a、b ab？ 交换a，b值的b=0？ a将a重新代入最大公约数，设b:回合的除数为a，馀数为b是否是否【参考资料】
1.https://www.zhi Hu.com/question/51427771 (初步答复) ) )。
2.brdzjy，jqdmht .图形算法使用Python .清华大学出版社. 2018