欧几里得算法

1. 核心定义

欧几里得算法（辗转相除法）是用于计算两个非负整数 $a, b$ 的最大公约数的高效算法。核心原理基于以下性质： $(a, b) = (b, a mod b)$

设 $r_{0} = a, r_{1} = b$ (假设 $a \geq b > 0$ )。进行连续带余除法：

r_{0} r_{1} r_{k - 2} r_{k - 1} = r_{1} q_{1} + r_{2}, = r_{2} q_{2} + r_{3}, ⋮ = r_{k - 1} q_{k - 1} + r_{k}, = r_{k} q_{k} + 0 0 < r_{2} < r_{1} 0 < r_{3} < r_{2} 0 < r_{k} < r_{k - 1} (整除，余数为 0)

则最后一个非零余数 $r_{k}$ 即为最大公约数 $(a, b)$ 。

# 核心：gcd(a,b) == gcd(b,a mod b)
def gcd(a,b):
	while b != 0:
		a,b = b,a % b
	return a

计算 $(198, 252)$ ：