整除和最大公约数。
如果m能整除n，记m|n。
对于不全为0的两个整数a和b，能同时整除他们俩的最大整数为它们的最大公约数，记为gcd(a,b)。如果gcd(a,b)=1，则a、b互质。
求gcd(a,b)可用欧几里德算法：
a = q1 * b + r1
b = q2 * r1 + r2
r1 = q3 * r2 + r3
r2 = q4 * r3 + r4
……
rn-3 = qn-1 * rn-2 + rn-1
rn-2 = qn * rn-1 + rn => rn就是gcd
rn-1 = qn+1 * rn + 0
欧几里德算法非常好写。以pascal语言为例：
function gcd(a,b:longint):longint;
begin
if b=0 then gcd:=a
else gcd:=gcd(b,a mod b);
end;
线性方程ax+by=c的解法。
对于a和b，ax+by是a和b的线性组合。这里x和y可以是任何整数。
令g=gcd(a,b)，则g整除所有的ax+by。特别地，所有ax+by的取值中，最小的正值为g。
因此，方程ax+by=c，仅当gcd(a,b)|c时有解。因此只考虑方程ax+by=gcd(a,b)的解法。
回忆上一章中讲的欧几里德算法，在第i步，我们有
ri-2 = qi * ri-1 + ri 。若ri+1=0,则ri就是gcd。
假设ri可表示为a和b的线性组合(xi,yi)，即ri=axi+byi，则有(xi,yi)=(xi-2,yi-2)-qi* (xi-1,yi-1)。
初始时， 由于a=q1*b+r1,即r1=a-b*q1,由序列{Rn}的通项公式Rn=R(n-2)-R(n-1)*q1,我们可以把a看做r(-1),
b看做,r0,那么对应于表达式ri=a*xi+b*yi,r(-1)=a=a*1+b*0=(1,0),r0=b=a*0+b*1=(0,1);
即r-1=a=(1,0)，r0=b=(0,1)。这样便可一步步推出rn=(xn,yn)，即为原方程的一组解。
因此有如下定理：
令a和b为非零整数，g=gcd(a,b)，则方程
ax+by=g 总可以通过欧几里德算法找出一组可行整解，记为(x1,y1)。它的通解可以表示为：
(x,y)=(x1+k*b/g , y1-k*a/g) ，其中k为任意整数。
竞赛中常用的欧几里德扩展算法采用的是倒推的方法，相比而言，本章提供的方法需要的变量稍多，常数稍大（只大了一点点）。但由于易于用迭代实现，而且实际测试中两种算法时间差别十分微小，因此本算法仍有应用价值。