欧几里得算法

欧几里得算法又称辗转相除法，是求最大公约数的算法。

[math]\displaystyle{ \forall a,b, \in N,b\not = 0, gcd(a,b) = gcd(b, a \;\mathrm{mod}\; b) }[/math] [math]\displaystyle{ }[/math]

证明

• 若 [math]\displaystyle{ a \lt b }[/math]

  [math]\displaystyle{ gcd(b, a \;\mathrm{mod}\; b) = gcd(b, a) = gcd(a, b) }[/math] ，命题成立

• 若 [math]\displaystyle{ a \geq b }[/math]

  不妨设 [math]\displaystyle{ a=q*b+r }[/math]，其中 [math]\displaystyle{ 0 \leq r \lt b }[/math]。显然[math]\displaystyle{ r=a \;\mathrm{mod}\; b }[/math]。

  对于 a,b 的任意公约数d，因为 [math]\displaystyle{ d|a,d|q*b }[/math]，故 [math]\displaystyle{ d|(a-qb) }[/math]，即 [math]\displaystyle{ d|r }[/math]，因此d也是b,r的公约数，反之亦成立。

  故a,b的公约数集合与 [math]\displaystyle{ b,a \;\mathrm{mod}\; b }[/math] 的公约数集合相同。于是它们的最大公约数自然也相等。

证毕。

实现

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

参考资料

1. 算法竞赛进阶指南，李煜东，143页