Euclid 规则：如果x和y都是正整数，而且x>=y，那么gcd(x,y)=gcd(x mod y, y)
假设x和y的gcd为a，那么必然有
x=a*n1
y=a*n2(gcd(n1,n2)=1)
那么我们求
x mod y
=>a*n1 mod a*n2
令x mod y=m,那么必然满足
x=n3*y+m
=>a*n1=n3*a*n2+m
=>m=a*(n1-n2*n3)
那么gcd(x mod y,y)就变成了gcd(a*(n1-n2*n3), a*n2),
如果gcd(n1-n2*n3,n2)不等于1，那么等式不成立
假设gcd(n1-n2*n3,n2)=k(k>1),
那么令
n1-n2*n3=n4*k
n2=n5*k
然后
n1=n2*n3+n4*k=n5*k*n3+n4*k=k(n3*n5+n4)
而n2=n5*k
于是gcd(n1,n2)>=k，于是与之前假设不成立，反证失效，证明完毕。