本节涉及最大公因数，辗转相除法求最大公因数，递推法求解线性组合，求解多元一次方程的整数解。

最大公因数

1.1定义

设a,b是两个不全为0的整数，若整数c满足, $c|a \ c|b,则称c为a、b的公因数,显然c的上确界不超过a,b的绝对值，故一定有最大公因数。$
$将最大公因数记作gcd(a,b)或是(a,b)。$

$若(a,b)=1则称a,b互素$

1.2最大公因数&辗转相除法求最大公因数

定理1

$设a,b是两个不全为0的整数,且a=qb+r,r\in Z,则(a,b)=(b,r)$

$prove:$
$\qquad let \ d=(a,b),d'=(b,r)$
$\qquad \because d|(a-qb),d|b$
$\qquad \therefore d \leq d'$
$\qquad \because d'|(qb+r) \ d'|b$
$\qquad \therefore d \geq d'$
$\qquad d=d',(a,b)=(qb+r,b)=(b,r)$

推论

$设a,b是两个不全为0的整数,q为整数,则(a,b)=(a \pm bq,b)=(a,b \pm aq)$

结合定理1及推论，我们可以得出一种方法，可以在有限步求取两个正整数的最大公因数

$let \quad r_0=a,r_1=b \quad r_0=r_1*q_1 +r_2$
$because (a,b)=(qb+r,b)=(b,r)$
$\therefore (r_i,r_{i+1})=(r_{i+1},r_{i+2}) \qquad 0\leq r_{i+2} < r_{i+1}$
$\because r_{i+1}>r_{i+2}$
$根据余项的递减关系，且两个整数有限大，故在有限步余数就会递减到零，此时r_n=(a,b),r_{n+1}=0$
$这就是辗转相除法，通过不断相除，余项不断递减，直到整除，从而得到最大公因数。$