浅谈辗转相除法的证明

什么是辗转相除法?

在说辗转相除法之前,我们需要知道一个概念最大公因子:最大公因子,又称最大公约数(英语:greatest common divisor,gcd),指两个或多个整数共同具有的最大约数(来自 百度百科)

举个例子,12 和 8 的最大公因子是多少? 显然我们可以直接得出结论是 4。但是当遇到大数的时候,比如:23454 和76862 的最大公因子是多少? 嗯~ o( ̄▽ ̄)o好像没那么容易一下子得出答案。

那辗转相除法如何求到的呢?

辗转相除法:又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。它的具体做法是:用较小数除较大数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。(来自 百度百科)

不BB,上代码:

#include<stdio.h>
int main():
{
    int a b; //求最大公约数的两个数
    int c; //最大公约数

    scanf("%d %d",&a,&b);
    if(a>b) //比较大小决定哪个是被除数
        c = euc(a,b);
    else
        c = euc(b,a);

    printf("最大公因子:%d", c);
    return 0;

}
int euc(int a,int b)
{
    int temp;
    int c;
    do{
        if(a%b==0) //如果除得尽,b就是最大公因子
            c = b;
        else{   //不然,将b 赋予被除数a,将余数赋予b,
            temp = b;
            b = a%b;
            a = temp;
        }

    }while(a%b==0);
    c=b; //将最终值赋予c

    return c;
}

从代码可以很直观的看到辗转相除法怎么求a,b最大公因子:

c=a%b ,如果c=0,则b就是最大公因子;不然,d=b%c 这样一直循环下去,最后就能求出最大公因子。

证明

首先我们得知道几个前提:

  • a 可以表示为 a = kb+c (c<b),实际上就是除法取余嘛
  • 为了方便,我们将a 和 b 的最大公因子表示为(a,b)

(敲黑板)有没有发现,要证明辗转相除法,实际就是证明 (a,b) =(b,c)。—(不信看看上面黑体字)

那么下面来证明 (a,b)为什么等于 (b,c):

  • 预备知识: '|' 是整除符号,比如 2|4,2|(4+6)
(a,b)|a, (a,b)|b, 因为 a = kb+c ,(b,c)|a  
  ==> (a,b) >= (b,c)  //b,c的最大公因子能整除a,但(b,c)不一定是a,b的最大公因子,所以大于等于

(b,c)|b, (b,c)|c , 因为c = a - kb ,(a,b)|c
    ==> (b,c) >=(a,b)   //同上

所以:(a,b) = (b,c)

既然证明了 (a,b)= (b,c),那么最后收尾阶段简单了:

(a,b)=(b,c)=(c,d)=…=(y,z)=z,就这么一直辗转相除下去,最终找到你的Mr.Right

后记

如果把等式展开,我们可以很直观地发现辗转相除法实质上是因数的分解。

辗转相除法证明不难,但是证明的时候在想一个问题:先是发现辗转相除法可以求最大公因子再有证明还是人们为了求最大公因子而发明了辗转相除法?诚然,我更愿意相信前者,因为人们总是喜欢发现规律再试图去总结规律;如果是后者,实在脑补不出来古希腊那群哔~是有多无聊。

通过这次证明,学习了如何去更加数学式地证明一个公式,
有兴趣的可以了解下 a,b最小公倍数=(a*b)/最小公因子 的证明,一样很有趣。

下回预告:浅谈中国剩余定理的证明