需要知识
<blockquote>
同余 
数论中的重要概念。给定一个正整数m，如果两个整数a和b满足（a-b）能够整除m，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。——百度百科
</blockquote>
关于<a href="/post/Algorithm/Congruence.html">同余</a>的定理
<h2 id="heading">欧几里德算法</h2>
<blockquote>
辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法， 其可追溯至3000年前。 
这种算法，在中国则可以追溯至东汉出现的《九章算术》。——百度百科 
简单明了的最大公因数计算算法。
</blockquote>

<pre style="background-color:#fff">int gcd(int a,int b){
 return b==0?a:gcd(b,a%b);
}
</pre>证明如下
<ol>
<li>有整数X，Y。其中，X=ar，Y=br(a,b互质，且r为最大公因数)。有X-Y=(a-b)*r。则，X、Y、X-Y互相间最大公因数相同。</li>
<li>有整数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互相间最大公因数相同。</li>
</ol>

欧几里得算法