辗转相位除法，最大公约数原理分析(码实现)首先说明原理分析码结语
前言
辗转除法很容易，但其原理自己不知道。 在那里看到了一些关于辗转相除原理的分析，在这里写下自己的理解。
解释lhdh算法也叫辗转相除，两个非负整数a，b的最大公约数应用领域包括数学和计算机两个方面。 计算公式gcd(a,b) = gcd(b,a mod b)。
也就是说，如果能将两个数除尽，则较小的数为最大公约数； 除不尽时，将较大的数替换为馀数，继续除以两个数取馀数。 在直到能够除尽的情况下，3358www.Sina.com/为最大公约数。
在原理分析中，首先，我们要求的2个数分别为较小的数(默认的ab )，a、b的最大公约数用a、b)表示。
3358www.Sina.com/=a(modb )即gcd(a,b是a除以b得到的r，
将r定义为a除以b得到的余数（remainder），即q。
辗转相除是指证明a和b的最大公约数和b和r的最大公约数相同
即gcd(a，b )=gcd(b ) b，r )。
前提条件：
商（quotient）(ab )
步骤ab=q…r，即c为a和b的最大公约数
ab=q…r
步骤2 :通过匹配假设，您可以看到盈馀c=gcd(a,b)已得到满足
r=a-qb
=Ac-qBc
=(a-QB ) c
从步骤2的结果中，c也为r的约数a=Ac，b=Bc为r，以及c和a，b的最大公约数的3http://ww。
第三步：
已知：
r=(a-QB ) c
b=Bc
目前，r和b分别有r和b两个约数。
因为c已经是公约数，所以那个公约数出现了c不仅是公约数，更是最大公约数，所以r和b的最大公约数是c。
步骤4 (证明(A-qB )和b互相质询(反证法) ) ) ) ) ) ) ) )。
我们在(A-qB )和b中添加了公约数（A-qB）和c
A-qB=B和c
B=如果我们能够证明(A-qB)与B互质的
根据公式，A=qB xd；
将a放回a=Ac :
a=(qbxd ) c，
将B=yd恢复为：
a=(qydxd ) c
a=(QYx )这两个因子中不再能够展开出其他公约数
b=y d (d1)
此时，3358www.Sina.com/与我们最初假设的3358www.Sina.com/相矛盾，表明d不存在。
(A-qB )与b的相互质量证明
假设(A-qB )与b互质，则c也是r和b的最大公约数，证明了gcd(A，b )=gcd(b ) b，r。
代码int a，b； scanf('%d，%d )，a，b )； 保证//A为较大的一方的数if(ab ) ({int c=a； a=b； b=c； //核心代码while () (a%b )！=0) {int r=a%b； a=b； b=r； 用结语求最大公约数的方法有很多，更多的方法可以参考这里。
其中辗转相除和更相减损法的原理比较相似，更相减损法的原理分析可参考此处
xd