欧几里得算法：修订间差异

2023年8月26日 (六) 15:53的最新版本

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

[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;
}

// 计算两个整数的最大公约数
int gcd(int a, int b) {
    // 如果b不为0，则递归调用gcd函数，参数为b和a除以b的余数
    return b ? gcd(b, a % b) : a;
}

@@ 第2行： / 第2行： @@
 <math>
-\forall a,b, \in N,b\not = 0, gcd(a,b) = gcd(b, a\mod b)
+\forall a,b, \in N,b\not = 0, gcd(a,b) = gcd(b, a \;\mathrm{mod}\; b)
 </math>
 <math></math>
 == 证明 ==
 * 若 <math>a < b</math>
-*: gcd(b, a mod b) = gcd(b, a) = gcd(a, b)，命题成立
+*: <math>gcd(b, a \;\mathrm{mod}\; b) = gcd(b, a) = gcd(a, b)</math> ，命题成立
 * 若 <math>a \geq b</math>
-*: 不妨设 <math>a=q*b+r</math>，其中 <math>0 \leq r < b</math>。显然<math>r=a mod b</math>。
+*: 不妨设 <math>a=q*b+r</math>，其中 <math>0 \leq r < b</math>。显然<math>r=a \;\mathrm{mod}\; b</math>。
 *: 对于 a,b 的任意公约数d，因为 <math>d|a,d|q*b</math>，故 <math>d|(a-qb)</math>，即 <math>d|r</math>，因此d也是b,r的公约数，反之亦成立。
-*: 故a,b的公约数集合与 <math>b,a mod b</math> 的公约数集合相同。于是它们的最大公约数自然也相等。
+*: 故a,b的公约数集合与 <math>b,a \;\mathrm{mod}\; b</math> 的公约数集合相同。于是它们的最大公约数自然也相等。
+证毕。
 == 实现 ==
@@ 第19行： / 第21行： @@
 }
 </syntaxhighlight>
+== 注释 ==
+<syntaxhighlight lang="c" line>
+// 计算两个整数的最大公约数
+int gcd(int a, int b) {
+    // 如果b不为0，则递归调用gcd函数，参数为b和a除以b的余数
+    return b ? gcd(b, a % b) : a;
+}
+</syntaxhighlight>
+== 参考资料 ==
+# 算法竞赛进阶指南，李煜东，143页
+[[Category:数学]]