欧几里得算法
又称为辗转相除法，c语言代码如下：
分析：a,b的关系可表示为a=kb+t,
即 a-kb=t, t=a%b,
假设c为a,b的一个公约数，将a-kb=t等式两边同除c，
得 a/c-kb/c=t/c,
因为等式左边为整数，所以t/c为整数，即c是t得约数，
所以c为b，t(a%b)的公约数，即a,b和b,a%b的公约数相同，即gcd(a,b)=gcd(b,a%b);
扩展欧几里得算法
c语言代码如下：
if(b)改为if(!b)
分析：有欧几里得算法可知gcd(a,b)=gcd(b,a%b),
对于不完全为0的非负整数，必然存在整数对x,y有gcd(a,b)=ax1+by1,
得gcd(b,a%b)=bx2+(a%b)y2=bx2+(a-a/b)y2=ay2+b(x2-(a/b)*y2),
即x1=y2,y1=x2-(a/b)*y2.