辗转相除.md

首先来确定是否任意$a,b$都有最高公因数

1. 若$b\mid a$，由定义可知，$b$就是$a,b$的最高公因数。同样的，如果$a\mid b$，$a$就是$a,b$的最高公因数

2. 若$b\not\mid a$，且$a\not\mid b$，因为任意整数都整除$0$，所以$a\ne 0$，$b\ne 0$

   $$ \begin{align} a&=q_1b+r_1\\ b&=q_2r_1+r_2\\ r_1&=q_3r_2+r_3\\ &\cdots\\ r_{k-2}&=q_kr_{k-1}+r_k\\ &\cdots\\ r_{n-2}&=q_nr_{n-1}+r_n\\ r_{n-1}&=q_{n+1}r_{n} \end{align} $$

   因为$r_1\lt|b|$，$r_2\lt|r_1|$，$\cdots$，所以最终一定能到达余数为$0$的情况

   由整除的性质7可知，$a,b$的公因数和$b,r_1$的公因数相同，$b,r_1$的公因数和$r_1,r_2$的公因数相同，$\cdots$，$r_{n-2},r_{n-1}$的公因数和$r_{n-1},r_n$的公因数相同。串在一块就是$a,b$的公因数和$r_{n-1},r_n$的公因数相同啦～

   观察到$r_n\mid r_{n-1}$，所以$r_n$就是$r_{n-1},r_n$的最高公因数，也就是$a,b$的最高公因数！

定理

1. 任意两个整数都有最高公因数，对两个整数使用辗转相除法得到的最后一个非零余项$r_n$就是它们的最高公因数

2. 任意两个整数$a,b$的最高公因数可以表示为$a,b$的线性组合

   $$ d=sa+tb $$

   其中$s,t$都是整数

   证明： ^608f36

   • 若$a$，$b$中有一个整除另一个，不妨假设$b\mid a$，则$d=b=0a+1b$，得证

   • 否则，不妨设$a=qb+r$，假设存在这样的$s'$和$t'$使得$gcd(b,r)=s'b+t'r$

     根据整除的性质7，$gcd(a,b)=gcd(b,r)$，因此只需证明存在$s$和$t$使得$sa+tb=s'b+t'r$

     $$ \begin{align} s(qb+r)+tb&=s'b+t'r\\ (sq+t)b+sr&=s'b+t'r \end{align} $$ 于是， $$ \begin{cases} s=t'\\ t=s'-sq=s'-t'q \end{cases} $$ 由于这样的$q$始终存在，所以这样的$s$和$t$始终能找到，于是得证