整除和最大公約數。
如果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為任意整數。
競賽中常用的歐幾里德擴展算法采用的是倒推的方法，相比而言，本章提供的方法需要的變量稍多，常數稍大（只大了一點點）。但由于易于用迭代實現，而且實際測試中兩種算法時間差別十分微小，因此本算法仍有應用價值。