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

来自吾萌百科
无编辑摘要
第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 \;\mathrm{mod}\; b)
</math>
</math>
<math></math>
<math></math>
== 证明 ==
== 证明 ==
* 若 <math>a < b</math>
* 若 <math>a < b</math>
*: <math>gcd(b, a \mod b) = gcd(b, a) = gcd(a, b)</math> ,命题成立
*: <math>gcd(b, a \;\mathrm{mod}\; b) = gcd(b, a) = gcd(a, b)</math> ,命题成立
* 若 <math>a \geq 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 的任意公约数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> 的公约数集合相同。于是它们的最大公约数自然也相等。


== 实现 ==
== 实现 ==

2022年2月24日 (四) 17:38的版本

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

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