最大公约数

一般使用 辗转相除法

辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
依照以下步骤执行:

1. 读入数a,b
2. 计算t=a mod b
3. 如果t是0,则说明b为a,b的最小公倍数,执行5;否则,执行4
4. a=b,b=t,跳到2
5. 输出b

证明

设两数为a、b(a>b)，用 \(gcb(a,b)\) 表示a，b的最大公约数，r=a (mod b) 为a除以b的余数，k为a除以b的商，即 \(a div b=k cdotscdots r\) 。辗转相除法即是要证明 \(gcb(a,b)=gcb(b,r)\) 。
第一步：令 \(c=gcb(a,b)\) ，则设 \(a=mc,b=nc\)
第二步：根据前提可知 \(r=a-kb=mc-knc=(m-kn)c\)
第三步：根据第二步结果可知， \(c\) 也是 \(r\) 的因数
第四步：可以断定 \(m-kn\) 与 \(n\) 互质（这里用反证法进行证明：设 \(m-kn=xd,n=yd(d>1)\) ，则 \(m=kn+xd=kyd+xd=(ky+x)d\) ，则 \(a=mc=(ky+x)cd,b=nc=ycd\) ，则a与b的一个公约数 \(cd>c\) ，故c非a与b的最大公约数，与前面结论矛盾，因此c也是b与r的最大公约数）从而可知 \(gcb(b,r)=c\) ，继而 \(gcb(a,b)=gcb(b,r)\) 。
证毕
注：以上步骤的操作是建立在刚开始时 \(r neq 0\) 的基础之上的，即m与n亦互质。

C++代码

    int gcb(int a,int b){
        while (1){
            int t=a%b;
            if (t==0) break;
            else {
                a=b;
                b=t;
            }
        }
        return b;
    }

最小公倍数

先求出a,b的最大公约数c,则最小公倍数 \(x=frac {a times b}{c}\)

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/12/