其中(x,y)为x和y的最大公约数
1. 若x=s*a，y=s*b，则(x,y)=s*(a,b)
证明：
对于一个质数，a拥有该质数的个数为ai,b拥有该质数的个数为bi,s拥有该质数的个数为si，而x拥有该质数的个数为ai+si,y拥有该质数的个数为bi+si。对于任何质数，都有min(si+ai，si+bi)=si+min(ai,bi),所以(x,y)=s*(a,b)。
如x=56,y=16,s=4,对于质数2，ai=1,bi=2,si=2,min(2+1，2+2)=2+min(1,2)。
2. gcd(x,y)= gcd(y,x%y) (x>=y)
证明：(其中[a]代表不大于a的最大整数)
设(x,y)=r,x=rx’,y=ry’,则(x’,y’)=1。
y=r*y’
x%y=x-[x/y]*y=rx’-[x/y]*ry’=r*(x’-[x/y]y’)
(y,x%y)=r*( y’, x’-[x/y]y’)
假设( y’, x’-[x/y]y’)不等于1，为k
则y’为k的倍数，x’-[x/y]y’为k的倍数，又因为[x/y]y’为k的倍数，则x’也为k的倍数，则(x’,y’)=k，而不等于1，所以假设不成立，( y’, x’-[x/y]y’)=1
所以(y,x%y)=r*( y’, x’-[x/y]y’)=r=(x,y)