最大公约数详解

2024-01-25 20:33:10

最大公约数详解

一般的，设 $a_1,a_2,...a_n$ ，是 $n$ 个非零整数，如果存在一个非零整数 $d$, 使得 $d\mid a_1,d\mid a_2,...d\mid a_n$ ，那么称 $d$ 是这 $n$ 个数的公约数。显然可能存在多个公约数，将这些公约数中最大的一个记为 $\gcd(a_1,a_2,...a_n)$ ，即最大公约数。

特别的，当 $\gcd(x,y)=1$ 的时候，二者显然互质。

辗转相除法

辗转相除法是用来求最大公约数的，也被称作欧几里得算法。

代码只有一行：

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

小常数版：

int gcd(int a,int b){
    if(a<b)return gcd(b,a);
    while(b){
        int t=a-a/b*b;
        a=b;b=t;
    }
    return a;
}

以下为证明部分（给出了多种证明，可以当跳过）

首先，最大公约数有以下三大性质（以下默认 $x>y>0$）

公约数都是最大公约数的约数
$\gcd(x,y)=\gcd(x,y-x)$
$\gcd(x,y)=gcd(y,x \bmod y )$

其中，第三条可以看作是对第二条的延伸

公约数都是最大公约数的约数

设 $x=k_1*d,y=k_2*d$

即 $d$ 为 $x,y$ 任意一个约数，不保证 $\gcd(k_1,k_2)=1\quad(d\ne\gcd(x,y))$，

设 $k_1=s_1*\gcd(k_1,k_2),k_2=s_2*\gcd(k_1,k_2)$

其中， $\gcd(s_1,s_2)$ 显然为 $1$，若不为 $1$，即 $s_1,s_2$ 仍有公因子，与 $\gcd$ 定义相违背

将 $k_1,k_2$ 带入 $x,y$ ,得 $x=s_1*\gcd(k_1,k_2)*d,y=s_2*\gcd(k_1,k_2)*d$

因为 $\gcd(s_1,s_2)=1$ ,所以 $gcd(x,y)=\gcd(k_1,k_2)*d$

所以 $d\mid\gcd(x,y)$

$\gcd(x,y)=\gcd(x,y-x)$

分类讨论：

设 $z\mid x,z\mid y$ 则 $z\mid(y-x)$
设 $z \nmid x$ ,则 $z$ 不是 $x$ 和 $y-x$ 的公因子
设 $z\mid x,z\nmid y$,则 $z$ 不是 $x$ 和 $y-x$ 的公因子

$\gcd(x,y)=gcd(y,x \bmod y)$

证明一

有 $\gcd(x,y)=\gcd(x,y-x)=\gcd(x,y-2x)=...=\gcd(x,y\bmod x)$

证明二

\[\gcd(x,y)=gcd(y,x \bmod y)\Leftrightarrow{\gcd(x,y)\mid \gcd(y,x\bmod y)\\\gcd(y,x\bmod y)\mid\gcd(x,y)} \]

设 $x=yq+r,(0\leq r<y)$

即 $r=x\bmod y$

设 $x=k_1*\gcd(x,y),y=k_2*\gcd(x,y)$

那么 $r=x-yq=k_1*\gcd(x,y)-k_2*\gcd(x,y)*q=\gcd(x,y)*(k_1-k_2q)$

所以 $\gcd(x,y)\mid\gcd(y,x\bmod y)$

因为 $x=yq+x\bmod y$

所以 $\gcd(y,x\bmod y)\mid\gcd(x,y)$

证明三

其实和证明二差不多。

$x$ 可以表示成 $x = qy + r (0\leq r<y)$，则 $r = x \bmod y$

假设 $d$ 是 $x,y$ 的一个公约数，即 $d\mid x,d\mid y$

而 $r = x - qy$，两边同时除以 $d$，$\frac rd=\frac xd-\frac{qy}d=m$，

由等式右边可知 $m\in \Z$ ，因此 $d|r$ ，$d$ 也是 $y,x \bmod y$ 的公约数

假设 $d$ 是 $y,x \bmod y$ 的公约数, 则 $d\mid y,d\mid (x-qy),q$ 是一个整数, 进而 $d\mid x$.

因此 $d$ 也是 $x,y$ 的公约数.

所以$x,y$ 和 $y,x \bmod y $ 的公约数集合是一样的，其最大公约数也必然相等。

裴蜀定理

也叫贝祖定理。

对任何整数 $a、b$ 和它们的最大公约数 $d$，关于未知数 $x$ 和 $y$ 的线性不定方程（称为裴蜀等式）：若 $a,b$ 是整数,且$\gcd(a,b)=d$，那么对于任意的整数 $x,y,ax+by$ 都一定是 $d$ 的倍数，特别地，一定存在整数 $x,y$，使$ax+by=d$ 成立。 ——百度百科

证明一

裴蜀定理也就是：

\[\left\{\begin{aligned}\forall x,y\to\gcd(a,b)\mid ax+by \\ax+by=\gcd(a,b)有整数解\end{aligned}\right. \]

其中 $a,b,x,y\in \Z$

第一个是显然的，来看看第二个。

这里还有一个引理

$ax+by$ 的最小正整数取值为 $\gcd(a,b)$

显然，如果这个引理成立，上面那个也成立：

设 $t=\gcd(a,b)$ 则 $t\mid a,t\mid b,t\mid ax+by$

设 $s$ 为 $ax+by$ 的最小正整数值，有 $s$ 为 $a,b$ 的线性组合，

设 $ r=a\bmod s,p=\lfloor\dfrac{a}{s}\rfloor$

$\therefore r=a-ps=a-p(ax+by)=a(1-px)-pby$

显然$r$也是$a,b$的线性组合

又 $\because s$ 最小 $\quad\therefore r=0$ （注意到前面 $r=a\%s$ ）

$\therefore s|a,s|b,$那么 $s$ 为 $a,b$ 的公因数 $\rightarrow t \ge s$

$\because t|ax+by\quad\therefore t|s$

$\therefore t \le s$

$\because t \ge s,t \le s$

$\therefore t=s$

证明二

反证法：https://blog.csdn.net/lleozhang/article/details/82935400

但这个证明有一个前提是扩展欧几里得。

推广

方程 $ax+by+cz+...+nm=f(a,b,c,...n,f\in\Z)$ 有整数解的充要条件是 $\gcd(a,b,c...n)\mid f$

应用

$\text{Luogu} 4549$ 【模板】裴蜀定理 https://www.luogu.com.cn/problem/P4549

注意题目中绝对值。

在模意义下的乘法逆元

即对于给定的 a，b，找到方程$aa^{-1}\equiv 1(\bmod b)$ 的一个整数解 $a^{-1}$

根据同余的定义，有 $b\mid(aa^{-1}-1)$，也就是存在整数 $k$ 使得 $bk=aa^{-1}-1$。移一下项，就得到了 $aa^{-1}-bk=1$

这个形式恰好符合裴蜀定理 $ax+by=1$ 的形式，于是我们可以通过扩展欧几里得计算出 $a^{-1}$

最小公倍数

插播一下最小公倍数~~（就是不讲扩展欧几里得）~~：

一般的，设 $a_1,a_2,...a_n$ ，是 $n$ 个非零整数，如果存在一个非零整数 $d$, 使得 $a_1\mid d,a_2\mid d,...a_n\mid d$ ，那么称 $d$ 是这 $n$ 个数的公倍数。显然存在无数多个公倍数，将这些公倍数中最小的一个记为 $\text{lcm}(a_1,a_2,...a_n)$ ，即最小公倍数。

一个有意思的东西是： $\gcd(x,y)\text{lcm}(x,y)=xy$

扩展欧几里得

如果您看了前面的内容，应该已经知道，扩欧（扩展欧几里得算法简称扩欧，或者 $exgcd$）是用来在已知 $a,b$ 的时候，求解一组 $p,q$ ，让 $pa+qb=\gcd(a,b)$

首先由裴蜀定理，解一定存在。

因为 $\gcd(a,b)=\gcd(b,a\bmod b)$ ，

所以 $pa+qb=\gcd(b,a\bmod b)=pb+q*a\bmod b=pb+q*(a-a/b*b)=qa+(p-a/b*q)b$

也就是说，$p=q,q=p-a/b*b$ 意味着 $p,q$ 改变，这是一个递归的转移。

其本质是将 $a$ 和 $b$ 的线性组合随着欧几里得算法的过程化简为 $b$ 和 $a\bmod b$ 的线性组合。

考虑递归边界：也即是辗转相除法的边界 $b=0$ ，显然有 $p=1,q=0$ ，回溯即可得到最原始的 $p,q$

int exgcd(int a,int b,int &x0,int &y0){//注意这里的引用
    if(b==0){//递归边界
        x0=1;y0=0;
        return a;
    }
    int r=exgcd(b,a%b,x0,y0);//求gcd(a,b)
    int temp=y0;
    y0=x0-(a/b)*y0;
    x0=temp;     //回溯
    return r;
}

程序中求到的 $x_0,y_0$ 仅仅是一组解，通解是：

$\forall t\in\Z,x=x_0+\frac b{\gcd(a,b)}t,y=y_0-\frac a{\gcd(a,b)}t$

其最小整数解 $x$ 应在 $t$ 取 $b$ 时。

参考

辗转相除法的严格证明 https://zhuanlan.zhihu.com/p/155667184

$\text{Luogu} 4549$ 【【模板】裴蜀定理】 https://aday526.blog.luogu.org/solution-p4549

码农公寓

最大公约数详解