辗转相除法的证明
辗转相除法的依据是：
- $\gcd(a,b) = \gcd(b, a \bmod b)\ (a,b \in \mathbb{N},\ a>b)$
- $\gcd(x,0) = x\ (x \in \mathbb{N})$
这里证明依据 1
求证：对于 $a,b \in \mathbb{N}\ 且\ a>b$，$a$ 与 $b$ 的最大公因数等于 $b$ 与 $a$、$b$ 余数的最大公因数
记 $a$、$b$ 余数为 $r$，$r = a - \lfloor \frac{a}{b} \rfloor \cdot b$
对 $a$ 和 $b$ 的任意公因数 $d$，有 $a=md$，$b=nd$ $(m,n,d \in \mathbb{N})$
$r = (m - \lfloor \frac{a}{b} \rfloor \cdot n)d$
$\because m - \lfloor \frac{a}{b} \rfloor \cdot n = \frac{a}{b} \cdot n - \lfloor \frac{a}{b} \rfloor \cdot n \in \mathbb{N}$
$\therefore d$ 也是 $b$ 与 $r$ 的公因数
对 $b$ 和 $r$ 的任意公因数 $d’$，有 $b=m’d’$，$r=n’d’$ $(m’,n’,d’ \in \mathbb{N})$
$a = (\lfloor \frac{a}{b} \rfloor \cdot m’ + n’)d’$
$\because \lfloor \frac{a}{b} \rfloor \cdot m’ + n’ \in \mathbb{N}$
$\therefore d’$ 也是 $a$ 与 $b$ 的公因数
综上所述，$a$ 与 $b$ 的公因数都是 $b$ 与 $r$ 的公因数，反之亦然。
$a$ 与 $b$ 的公因数集合和 $b$ 与 $r$ 的公因数集合相同。
因此 $a$ 与 $b$ 的最大公因数也是 $b$ 与 $r$ 的最大公因数。