辗转相除法：
辗转相除法最大的用途就是用来求两个数的最大公约数。
用（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
辗转相除法比较适合用来求两个比较大的数的最大公约数 。后附代码
拓展的欧几里得算法计算乘法逆元：
后附代码。
int divisor(int m,int n)
{if (m % n == 0) {return n;}else {return divisor(n,m % n);}
}
/*
欧几里德算法：辗转求余
原理： gcd(a,b)=gcd(b,a mod b)
当b为0时，两数的最大公约数即为a
getchar()会接受前一个scanf的回车符
*/
#include<stdio.h>
unsigned int Gcd(unsigned int M,unsigned int N)
{unsigned int Rem;while(N > 0){Rem = M % N;M = N;N = Rem;}return M;
}
int main(void)
{int a,b;scanf("%d %d",&a,&b);printf("the greatest common factor of %d and %d is ",a,b);printf("%d\n",Gcd(a,b));return 0;
}
/*拓展的欧几里得算法
*/
void exgcd(int a,int b,int &x,int &y)
{if(b==0){ x=1; y=0; return;}exgcd(b,a%b,x,y);int tp=x;x=y; y=tp-a/b*y;
}