摘要：
给定一个正整数m，如果两个整数a和b满足（a-b），并且可以被m除，即（a b）/m产生一个整数，则称整数a和b与模m一致，该模被记录为→b、 m同余是整数的等价关系——百度百科同余定理欧几里德算法转向除法，也称欧几里德算法，是一种寻找两个正整数的最大公因子的算法。它是已知最古老的算法，可以追溯到3000年前。这个算法可以追溯到中国东汉时期的《九章算术》——百度百科是计算最大公因子的一个简单明了的算法。
需要知识
欧几里德算法
这种算法，在中国则可以追溯至东汉出现的《九章算术》。——百度百科
简单明了的最大公因数计算算法。
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
证明如下
- 有整数X，Y。其中，X=a*r，Y=b*r(a,b互质，且r为最大公因数)。有X-Y=(a-b)*r。则，X、Y、X-Y互相间最大公因数相同。
- 有整数X，Y。其中，X=a*r+c，Y=b*r+d(r为最大公因数，且c，d小于r)。设e=X%Y，也即(e+d+b*r)*n=a*r+c，有e=a*r+c-d-b*r=(a-b)*r+(c-d)，所以X、Y、X%Y互相间最大公因数相同。