欧几里得算法定理 $gcd(a,b)=gcd(b,a \bmod b)$证明：设 $p$ = $\lfloor a/b \rfloor$，则 $a = b \cdot p + m, a \bmod b = m$。因为 $a$ 和 $b$ 是 $gcd (a,b)$ 的倍数，所以 $b \cdot p, b \cdot p + m$ 是 $gcd (a,b)$ 的倍数，因此 $m$ 是 $gcd (a,b)$ 的倍数。所以 $gcd (a,b)$ 是 $m, b$ 的因数。又因为 $gcd (b, a \bmod b) = gcd (b, m)$，即 $gcd (b, a \bmod b)$ 是 $b, m$ 的最大公因数，所以 $gcd (a,b)$ 是 $gcd (b, a \bmod b)$ 的因数。同理，$b$ 和 $m$ 是 $gcd (b,m)$ 的倍数，所以 $b \cdot p + m$ 即 $a$ 是 $gcd (b, m)$ 的倍数。所以 $gcd (b,m)$ 是 $a$ 与 $b$ 的因数。又因为 $gcd (a,b)$ 是 $a,b$ 即 $b \cdot p
ybaggio
