最大公约数、扩展欧几里得算法和最小公倍数

参考资料： 1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c

2.余红兵：《数学奥林匹克小丛书（第二版）高中卷10————数论》

最大公约数

设$a,b\in Z$，如果$d\in Z$且$d|a,d|b$，则称$d$是$a$和$b$的公因子（公约数）。 若$d\ge 0$，且$a$和$b$的所有公因子都整除$d$，则称$d$是$a$和$b$的最大公约数，记作$\gcd(a,b)$。

之前CSDN上我也写过一篇gcd筛： https://blog.csdn.net/hustle28214/article/details/128601837?spm=1001.2014.3001.5501

互素

设$a,b\in Z$，若$\gcd(a,b)=1$，则称$a$和$b$互素。 互素的$a,b$公因子仅有$\pm 1$，该条件可反推出$a,b$两数互素。

根据定义有结论： 设$\gcd(a,b)=d$，则存在$q_1,q_2\in Z$，使得$a=q_1 d,b=q_2 d$，且$\gcd(q_1,q_2)=1$。

若$\gcd(q_1,q_2)=t>1$，则$\gcd(a,b)=td>d$，与“最大”矛盾。

欧几里得算法（辗转相除法）

设$a\ge b\ge 0$，求$\gcd(a,b)$ 对于上述条件下的$a,b$，有$a=qb+r$； $b=0$时，$\gcd(a,0)=a$ $b>0$时，$\gcd(a,b)=\gcd(b,r)=\gcd(r_1,r_2)$

$\gcd(a,b)=\gcd(b,r)$这条推广有必要演示一下： $\gcd(40,3)=1$ $\gcd(40,3)=\gcd(3,1)=\gcd(1,0)=1$ 依次如此操作直到见到0

int gcd(int x, int y)
{
    int r = x % y;
    while (r != 0)
    {
        x = y;
        y = r;
        r = x % y;
    }    
return y;//最大公约数实现
 
}

扩展欧几里得算法

(重要)定理5-1（最大公约数表示定理）（裴蜀定理）

设$a,b\in Z$，$d=\gcd(a,b)$，则存在$s,t\in Z$，使得$as+bt=d$。

特别地：$\gcd(a,b)=1$ ———— $as+bd=1$（充要）

推论：$d|v$ ———— $as+bt=v$

证明：

设$b\ge a$，$b=ax_1+r_1$，那么$b$后$b=r_1$。

重复辗转相除直至余数为0。

$b=ax_1+r_1$， $a=r_1x_2+r_2$， ......， $r_{k-3}=r_{k-2}x_{k-1}+r_{k-1}$ (2) $r_{k-2}=r_{k-1}x_k+r_k$，(1) $r_{k-1}=r_kx_{k+1}+r_{k+1}$。

此时$r_{k+1}=0$（余数）。由此得出$r_k=d$（最大公约数）。将此式代入(1)式，移项得到$d=r_{k-2}-r_{k-1}x_k$。

将此式与(2)式联立，得到$d=r_{k-2}-(r_{k-3}-r_{k-2}x_{k-1})x_k$。

展开，得到$d=m_1 r_{k-2}-n_1 r_{k-3}$。

上述所有提及皆为整数，则$m_1(1-x_{k-1}x_k)$，$n_1(-x_k)$必为整数。

相同的操作可以重复做，不断带入之前的式子可以发现最后可以化成$d=m_k a+n_k b$。

而显然$m_k,n_k$为整数。

证毕。

对于第二条“特别地”的证明如下：

假设$\gcd(a,b)\neq 1$。

那么，将$a$表示为$k_1 \gcd(a,b)=a$，$b=k_2 \gcd(a,b)$。

代入$as+bd=1$：$k_1 \gcd(a,b)s + k_2 \gcd(a,b)r = 1$。

即，$(k_1 s + k_2 r) = 1/\gcd(a,b)$

那么右式取值区间为$(0,1)$，显然无法满足整数解性质。

所以$\gcd(a,b)=1$才能使$as+bd=1$有整数解。

想一想，如果要证其必要性，则假设$as+bd=1$没有整数解，右式$=1$，也必定存在$s,d\in Z$使得方程有解。

第三条推论自不必说，$v$是$d$的整数倍。

所以，扩欧相对于欧几里得算法的扩展性就是：使用欧几里得算法时，利用余数和商向上迭代出$s_n,t_n$。这同样也是在计算二元一次不定方程。

通过扩欧我们可以找到判断二元一次不定方程是否有整数解的方法：

对于方程$ax+by=z$，只有满足$\gcd(a,b)|z$，方程才有整数解。

最小公倍数

设$a,b\in Z$，若$m\in Z$分别是$a$和$b$的倍数，$m$称为$a$和$b$的公倍数。

记$a,b$的最小公倍数为$\mathrm{lcm}(a,b)$，若$m$是$a$和$b$所有正的公倍数中最小，$m$称作$a$和$b$的最小公倍数。

$\mathrm{lcm}(a,b) = \frac{ab}{\gcd(a,b)}$。

我在CSDN那篇上写“最小公倍数的求算依赖于最大公约数的求算”，其实这有些以偏概全，求最小公倍数的算法并不止这一种。下面就记录一下这种不需要找最大公约数的神奇算法（更相增益术/更相减损术）： 设有两正整数$0\<a\<b$。

$a$更小，$a$自加成$2a$；此时若发现$b$更小，$b$自加，成$2b$；...；若发现$a$更小，$a$自加，直到$2k a = 2k-1 b$。那么$2k a$就等于$\mathrm{lcm}(a,b)$。

int lcm(int a,int b)
{
    while(a!=b)
    {
        if(a\<b)
        a+=a;
        else if(b\<a)
        b+=b;

    }
    return a;
}