需要知识

同余
数论中的重要概念。给定一个正整数m，如果两个整数a和b满足（a-b）能够整除m，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。——百度百科

关于同余的定理

欧几里德算法

辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法， 其可追溯至3000年前。
这种算法，在中国则可以追溯至东汉出现的《九章算术》。——百度百科
简单明了的最大公因数计算算法。

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

证明如下

1. 有整数X，Y。其中，X=ar，Y=br(a,b互质，且r为最大公因数)。有X-Y=(a-b)*r。则，X、Y、X-Y互相间最大公因数相同。
2. 有整数X，Y。其中，X=ar+c，Y=br+d(r为最大公因数，且c，d小于r)。设e=X%Y，也即(e+d+br)n=ar+c，有e=ar+c-d-b*r=(a-b)*r+(c-d)，所以X、Y、X%Y互相间最大公因数相同。