整除和最大公約數(shù)。
如果m能整除n，記m|n。
對(duì)于不全為0的兩個(gè)整數(shù)a和b，能同時(shí)整除他們倆的最大整數(shù)為它們的最大公約數(shù)，記為gcd(a,b)。如果gcd(a,b)=1，則a、b互質(zhì)。
求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的解法。
對(duì)于a和b，ax+by是a和b的線性組合。這里x和y可以是任何整數(shù)。
令g=gcd(a,b)，則g整除所有的ax+by。特別地，所有ax+by的取值中，最小的正值為g。
因此，方程ax+by=c，僅當(dāng)gcd(a,b)|c時(shí)有解。因此只考慮方程ax+by=gcd(a,b)的解法。
回憶上一章中講的歐幾里德算法，在第i步，我們有
ri-2 = qi * ri-1 + ri 。若ri+1=0,則ri就是gcd。
假設(shè)ri可表示為a和b的線性組合(xi,yi)，即ri=axi+byi，則有(xi,yi)=(xi-2,yi-2)-qi* (xi-1,yi-1)。
初始時(shí)， 由于a=q1*b+r1,即r1=a-b*q1,由序列{Rn}的通項(xiàng)公式Rn=R(n-2)-R(n-1)*q1,我們可以把a(bǔ)看做r(-1),
b看做,r0,那么對(duì)應(yīng)于表達(dá)式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為非零整數(shù)，g=gcd(a,b)，則方程
ax+by=g 總可以通過歐幾里德算法找出一組可行整解，記為(x1,y1)。它的通解可以表示為：
(x,y)=(x1+k*b/g , y1-k*a/g) ，其中k為任意整數(shù)。
競(jìng)賽中常用的歐幾里德擴(kuò)展算法采用的是倒推的方法，相比而言，本章提供的方法需要的變量稍多，常數(shù)稍大（只大了一點(diǎn)點(diǎn)）。但由于易于用迭代實(shí)現(xiàn)，而且實(shí)際測(cè)試中兩種算法時(shí)間差別十分微小，因此本算法仍有應(yīng)用價(jià)值。