欧几里得算法（辗转相除法）

在一个除法算式中，被除数与除数的最大公因数等于除数与余数的最大公因数，这是辗转相除法用于计算最大公因数的最根本的依据。
辗转相除法就是反复应用上述规律（被除数与除数的最大公因数等于除数与余数的最大公因数）得到一系列的算式，后一个算式是将前一个算式的除数和余数分别作被除数和除数进行的除法，最后一个不等于0的余数就是所求的最大公因数。

给定a,b两个数，假设a>b,那么（a,b)=(b,a-b)
再确定b,a-b大小,
用大数减小数，重复这个过程直到其中有一个数整除另一个数，这个数就是最大公约数

就是把上一轮有余数的除法计算中，
除数变为下一轮计算的被除数，
余数变为下一轮计算的除数，
一直这样计算下去，
直到最后一次计算余数为零，
在最后一轮计算中的被除数，即为所求的最大公约数。
举例：
105和85的最大公约数
第一轮计算
105÷85=1...20
第二轮计算
85÷20=4...5
第三轮计算
20÷5=4
第三轮没有余数，
因此
105和85的最大公约数就是第三轮计算的被除数
5.
至于C语言编程，下边是我自己写的G函数(思想就是辗转相除法求最大公约数)
int
G(int
x,int
y)
{
int
t;
while(y!=0)
{
t=x%y
;
x=y;
y=t;
}
return
x;
}