（创建页面，内容为“'''欧几里得算法'''又称'''辗转相除法'''，是求最大公约数的算法。 <math> \forall a,b, \in N,b\not = 0, gcd(a,b) = gcd(b, a mod b) </math> <math></math> == 证明 == * 若 <math>a < b</math> *: gcd(b, a mod b) = gcd(b, a) = gcd(a, b)，命题成立 * 若 <math>a \geq b</math> *: 不妨设 <math>a=q*b+r</math>，其中 <math>0 \leq r < b</math>。显然<math>r=a mod b</math>。 *: 对于 a,b 的任意公约数d，因为 <math>d|a,d|q*b</mat…”） |
无编辑摘要 |
||
| 第2行： | 第2行： | ||
<math> | <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 \mod b) | ||
</math> | </math> | ||
<math></math> | <math></math> | ||
2022年2月24日 (四) 17:34的版本
欧几里得算法又称辗转相除法，是求最大公约数的算法。
[math]\displaystyle{ \forall a,b, \in N,b\not = 0, gcd(a,b) = gcd(b, a \mod b) }[/math] [math]\displaystyle{ }[/math]
证明
- 若 [math]\displaystyle{ a \lt b }[/math]
- gcd(b, a mod b) = gcd(b, a) = gcd(a, b)，命题成立
- 若 [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 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 mod b }[/math] 的公约数集合相同。于是它们的最大公约数自然也相等。
实现
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}