深入浅出理解欧几里得算法的原理

欧几里得算法

一、干什么用？

算出最大两个非负整数的最大公约数。虽然小学知识，大家概念很清楚，但我们这里还是提下，能被两个数A，B整除的最大整数C，就称C是A和B的最大公约数。可以用GCD（A,B）表示。GCD是Greatest Common Divisor的缩写。

二、欧几里得算法的内容

欧几里得是快速找出两个数最大公约的一种算法。算法核心思想：

例如找A，B的最大公约数GCD（A,B），并且A>B

• 如果A=0，那么GCD（A，B）=GCD（0，B）=B；
• 如果B=0，那么DCD（A，B）=GCD（A，0）=A；
• 用余数表示A，A=B*Q+R，Q表示B的几倍，R是余数。
• GCD（A,B）=GCD（B，R）

举例说明：

A=12，B=8；

由12 = 8*1+4；根据欧几里得算法得到GCD（12,8）=GCD（8,4）；

然后A=8，B=4；

由8 = 4*2+0；根据欧几里得算法得到GCD（8,4）=GCD（4,0）；

因为A！=0，B=0，所以GCD（4,0）=4；

以上我们可以得出：GCD（12,8）=GCD（8,4）=GCD（4,0）=4；

从上面的例子中我们可以看到欧几里得算法，他把一个复杂的问题逐渐简化成了简单问题。这种算法思想就是通常我们说的：分治思想（Divide and Conquer）。

三、证明欧几里得思想

1.证明GCD（A，0）=A

• 我们知道A的最大公约数是A；
• A*0=0；即0除以任何整数都是0；因此我们可以说任何数都可以是0的约数。
• 因为A大于0，所以GCD（A，0）=A；

同理我们可以证明出：GCD（B，0）=B。

2.证明GCD（A,B）=GCD（B，R）

要想证明GCD(A,B)=GCD(B,R)，首先我们需要证明GCD(A,B)=GCD(B,A-B)；

先上图：

三个数，A,B,C，满足A-B=C；

图的左侧说明：

GCD（A，B）是A和B的最大公约数，同时就说明其能整除A和B;可以将其表示为：

X*GCD（A，B）=A；Y*GCD（A，B）=B；

得到：A-B=X*GCD（A，B）-Y*GCD（A，B）=（X-Y）*GCD（A，B）=C

==>GCD（A，B）也是C的一个约数；

图的中间说明：

GCD（B，C）是B和C的最大公约数，同时就说明其能整除B和C;可以将其表示为：

M*GCD（B，C）=B；N*GCD（B，C）=C；

得到：B+C=M*GCD（B，C）+N*GCD（B，C）=（M+N）*GCD（B，C）=A

==>GCD（B，C）也是A的一个约数；

图的右侧说明：

• GCD（A，B）是B的约数，同时也是C的约数，算是B和C的一个公共约数，但是肯定小于或等于B和C的最大公约数，
• 所以GCD（A，B）<=GCD（B，C）;
• GCD（B，C）是A的约数，同时也是B的约数，算是A和B的一个公共约数，但是肯定小于或等于A和B的最大公约数
• 所以GCD（B，C）<=GCD（A，B）；
• 最终得出GCD（A，B）=GCD（B，C）=GCD（B，A-B）

我们证明了GCD(A,B)=GCD(B,A-B)，接下来我们证明GCD(A,B)=GCD(B,R)。

GCD(A,B)=GCD(B,A-B)可以写成GCD(A,B)=GCD(A-B,B)

由GCD(A,B)=GCD(A-B,B)可以得出GCD(A-B,B)=GCD(A-2B,B)

以此类推：GCD(A,B)=GCD(A-B,B)=GCD(A-2B,B)==GCD(A-3B,B)=GCD(A-Q*B,B)

因为A可以表示成：A=Q*B+R;将其代入到GCD(A-Q*B,B)中得到：

GCD(（Q*B+R）-Q*B,B)=GCD(R,B)=GCD(B,R)；

进一步得到：GCD(A,B)=GCD(B,R)