数论基础

【第二讲】

第二讲我们要学习的概念有：

欧几里得算法
裴蜀定理
扩展欧几里得算法

一、欧几里得算法

在第一讲中我们知道了 gcd 的概念，现在我们来介绍如何计算两个整数 $a,b$ 的 $\gcd$

首先我们需要知道 $\gcd$ 的一个重要性质，

\gcd(a,b)=\gcd(a-b,b)=\gcd(a\mod b,b)

证明：

（1） $\gcd(a,b)=\gcd(a-b,b)$

设 $d$ 是 $a$ 和 $b$ 的任意一个公约数，即 $d|a$ 且 $d|b$ ，依据整除的性质：

若 $d|a$ 且 $d|b$ ，则 $d|(x-y)$

反过来，设 $d$ 是 $b$ 和 $(a-b)$ 的任意一个公约数，即 $d|b$ 且 $d|(a-b)$ ，同样根据整除的性质：

若 $d|x$ 且 $d|y$ ，则 $d|(x+y)$

因此，由 $d|b$ 和 $d|(a-b)$ 可得到 $d|[b+(a-b)]=a$

这也说明 $d$ 也是 $a$ 和 $b$ 的公约数

综上所述， $a$ 和 $b$ 的所有公约数与 $b$ 和 $(a-b)$ 的所有公约数完全相同，由于 $\gcd$ 是公约数集合中最大的元素，因此两者的最大公约数必然相等，即
$\gcd(a,b)=gcd(a-b,b)$
（2） $\gcd(a,b)=\gcd(a\mod b,b)$

根据带余除法的定义：

对于两个整数 $a,b$ （ $b\ne0$ ），存在唯一的整数 $q$ （商）和 $r$ (余数)，使得：
$a=b\cdot q+r$
其中 $r=a\mod b$

利用第一步的结论，我们可以反复使用 $\gcd(a,b)=gcd(a-b,b)$

1）第一次： $\gcd(a,b)=gcd(a-b,b)$

2）第二次： $gcd(a-b,b)=gcd((a-b)-b,b)=gcd(a-2b,b)$

...

q）第 $q$ 次： $gcd(a-(q-1)b,b)$ = $gcd(a-qb,b)$

而由带余除法 $a=b\cdot q+r$ 可知， $a-qb=r$ （即 $a\mod b$ ）

因此， $\gcd(a,b)=\gcd(r,b)=gcd(a\mod b,b)$

然后我们知道 $\gcd(a,b)=\gcd(b,a)$ ，于是得到：

\gcd(a,b)=\gcd(b,a-b)

这个式子又称作 “更相减损术”

\gcd(a,b)=\gcd(b,a\mod b)

这个式子又称作 ”辗转相除法”

显然，如果不停地使用这两个式子，总能将 $b$ 化成 $0$ ，于是就能得到 $\gcd(a,0)=a$

并且对于两个整数 $a,b$ ，使用 “辗转相除法” 需要的循环次数一定小于等于 "更相减损术" ，这里省略证明，留给读者自证。

Task 1: 证明上述结论

因此，我们采用计算次数更少，也就是计算复杂度更低的 “辗转相除法” 来计算 $\gcd(a,b)$ ，下面来看个例子：

例： $\gcd(84,30)$

（1） 第一次操作

初始输入 $a=84,b=30$ ，依据公式，先计算 $a\mod b=84\mod 30=24$

于是 $\gcd(84,30)=\gcd(30,84\mod 30)=\gcd(30,24)$ ，这个时候 $a=30,b=24$ ，就完成了一次辗转相除操作

（2） 第二次操作

此时输入 $a=30,b=24$ 依据公式，先计算 $a\mod b=30\mod 24=6$

于是 $\gcd(30,24)=\gcd(24,30\mod 24)=\gcd(24,6)$ ，这个时候 $a=24,b=6$ ，就完成了第二次辗转相除操作

（3） 第三次操作

此时输入 $a=24,b=6$ ，依据公式，先计算 $a\mod b=24\mod 6=0$

于是 $\gcd(24,6)=\gcd(6,24\mod 6)=\gcd(6,0)$ ，这个时候 $a=6,b=0$ ，就完成了第三次辗转相除操作

（4）根据 $\gcd$ 的性质， $\gcd(6,0)=6$ ，计算完成

所以， $\gcd(84,30)=6$

让我们使用代码来实现这个过程

递归写法 ：

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

循环写法：

int gcd(int a,int b){
    while (b != 0){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

恭喜你！学会了 欧几里得算法 ！也就是上述的 "辗转相除法"

二、裴蜀定理

又称 贝祖定理 ，内容如下：

对于任意整数 $a,b$ ，存在整数 $x$ 和 $y$ ，使得以下等式成立：

ax+by=d

其中 $\gcd(a,b)|d$

我们称这一组系数 $x,y$ 为 贝祖系数

特殊情况：

当 $a,b$ 均为质数时，即 $\gcd(a,b)=1$ ，存在整数 $x,y$ 满足

ax+by=1

简而言之，裴蜀定理表明：

两个整数的最大公约数，是这两个数所有整数线性组合中最小的正整数，并且所有能表示为 $ax+by$ 的整数，都是它们最大公约数的倍数

扩展：

我们考虑数组 $\{a_i\}$ ，可以扩展裴蜀定理得到，存在系数数组 $\{x_{i}\}$ 使得

\sum_{i=1}^{n}a_{i}x_{i}=d

其中 $gcd(a_{1},a_{2},...,a_{n})|d$

Task 2:

思考
$\sum_{i=1}^{n}(a_{i}x_{i}+b_{i}y_{i})$
这个式子具有什么性质？

Task 3:

思考

对于二维数组（矩阵） $\{A_{i}\}=\{a_{i},b_{i},c_{i},...\}$ 和

另一个二维数组（矩阵） $\{B_{i}\}=\{x_{i},y_{i},z_{i},...\}$ 是否也有类似性质？

三、扩展欧几里得算法

引入：

给定一个线性不定方程

ax+by=c

已知 $a,b,c$ ，请你求出系数 $x,y$ 的一组解

聪明的你一定发现了！诶？这个方程长得好像刚学的 裴蜀定理 啊！

让我们来回顾一下 裴蜀定理 的内容：

对于任意整数 $a,b$ ，存在整数 $x$ 和 $y$ ，使得以下等式成立：

ax+by=d

其中 $\gcd(a,b)|d$ ，也就是说 $d$ 一定是 $\gcd(a,b)$ 的倍数

所以合理猜测，如果 $c$ 也是 $\gcd(a,b)$ 的倍数，那么我们就知道这个方程是可解的，并且 $x,y$ 就是贝祖系数 ；反之，如果 $c$ 不是 $\gcd(a,b)$ 的倍数，貌似应该解不出来整数 $x,y$ 满足上述方程

我们来证明一下：

（1）当 $c$ 是 $\gcd(a,b)$ 的倍数时，方程 $ax+by=c$ 有解

设 $g=\gcd(a,b)$ ，若 $g|c$ （即 $c$ 是 $g$ 的倍数），则存在整数 $k$ 使得 $c=k\cdot g$ ，依据裴蜀定理，存在：
$ax_{0}+by_{0}=g$
将等式两边同时乘以 $k$ ，得：
$a(kx_{0})+b(ky_{0})=k\cdot g=c$
此时，取 $x=kx_{0},y=ky_{0}$ （均为整数），则 $ax+by=c$ 成立，因此方程有解。

实例：

方程 $84x+30y=12$ ， $g=\gcd(a,b)=\gcd(84,30)=6$ ，有裴蜀定理，存在 $x_{0},y_{0}$ 使得 $84x_{0}+30y_{0}=\gcd(84,30)=6$ ，可以解得 $x_{0}=-1,y_{0}=3$

两边同时乘以 $k=\frac{c}{g}=\frac{12}{6}=2$ 得到
$84\times (-2)+30\times 6=12$
验证成立

（2）当 $c$ 不是 $\gcd(a,b)$ 的倍数时，方程 $ax+by=c$ 无解

假设方程 $ax+by=c$ 存在整数解 $x,y$ ，由于 $g=\gcd(a,b)$ ，根据最大公约数的性质 $g|a$ 且 $g|b$ ，根据整除的性质：

若 $d|m$ 且 $d|n$ ，则 $d|(mx+ny)$ （ $x,y$ 均为整数）

因此， $g|(ax+by)$ ，即 $g|c$ ，与假设相矛盾，故假设不成立，方程无解

原来如此！也就是说，我们要判断方程 $ax+by=c$ 是否有解，只需要判断 $c$ 是否是 $\gcd(a,b)$ 的倍数就行了！原来裴蜀定理中“ $\gcd(a,b)|d$ ”是“ 方程有解 ” 的 充要条件 ！

那么有同学就要问了，老师老师，你还是没有讲怎么求解贝祖系数 $x,y$ 呀！

别急，我们来整理一下知识：

对于方程 $ax+by=\gcd(a,b)$ ，依据裴蜀定理知道一定存在一组贝祖系数 $x,y$ 使得该方程成立，对于 $\gcd(a,b)$ ，我们知道可以使用”辗转相除法”，也就是 欧几里得算法 来求解，我们来模拟一下这个过程

$\gcd(a,b)=\gcd(b,a\mod b)$ ，也就是将方程变为 $bx'+(a\mod b)y'=g$ ，这时候我们需要来观察一下贝祖系数的变化，容易看出，在 $a,b$ 辗转相除的过程中，贝祖系数 $x,y$ 也一定是在变化的（ $x',y'$ 表示经过辗转相除后变化的贝祖系数）

我们来定义两个初始状态，当 $a\cdot 1+b\cdot 0=a$ 时，我们称这时候的 $a=a_{0}$

当 $a\cdot 0+b\cdot 1=b$ 时，我们称这时候的 $b=b_{0}$

也就是初始输入为 $\gcd(a_{0},b_{0})$ ，辗转之后 $a=b_{0},b=a_{0}\mod b_{0}$ ，合理猜测，辗转之后的 $a,b$ 能否用 $a_{0},b_{0}$ 表示出来？

于是得到方程组

\begin{cases} a=a_{0}\cdot x_{1}+b_{0}\cdot y_{1} \\ b=a_{0}\cdot x_{2}+b_{0}\cdot y_{2} \end{cases}

容易证明存在两组贝祖系数满足这个方程，留给读者自证

Task 4

思考如何证明一定存在两组整系数 $x_{1},y_{1},x_{2},y_{2}$ 满足上述方程

这时再次进行辗转相除，得到新一轮的 $a,b$

我们将上述方程组带入辗转的过程中得到

首先将 $a$ 赋值成 $b$

a=a_{0}\cdot x_{1}+b_{0}\cdot y_{1}=b=a_{0}\cdot x_{2}+b_{0}\cdot y_{2}

可以发现

\begin{cases} x_{1}=x_{2} \\ y_{1}=y_{2} \end{cases}

再将 $b$ 赋值成 $a\mod b$

a\mod b=r=a-b\cdot \lfloor \frac{a}{b} \rfloor

这里我们用 $q$ 表示 $\lfloor \frac{a}{b} \rfloor$ ，于是带入得到

b=a_{0}\cdot x_{2}+b_{0}\cdot y_{2}=a-bq=(a_{0}\cdot x_{1}+b_{0}\cdot y_{1})-(a_{0}\cdot x_{2}+b_{0}\cdot y_{2})q

化简得到

b=a_{0}\cdot x_{2}+b_{0}\cdot y_{2}=(x_{1}-x_{2}q)a_{0}+(y_{1}-y_{2}q)b_{0}

可以发现

\begin{cases} x_{2}=x_{1}- x_{2}q\\ y_{2}=y_{1}- y_{2}q \end{cases}

这样我们就成功找出了每一次辗转过程中这两组贝祖系数的变化

我们使用代码来实现这个过程

C++:

在 C++ 里，y1 属于标准数学库函数，其作用是计算第一类贝塞尔函数（即 Neumann 函数）的值，所以我们这里使用 $x,y,x2,y2$ 来表示两组贝祖系数（如果你不用万能头就可以正常使用 $x_{1},y_{1},x_{2},y_{2}$ ）

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int& x, int& y){
    x = 1; y = 0;
    int x2 = 0; int y2 = 1;
    while (b != 0){
        int q = a / b;
        tie(a, b) = make_tuple(b, a % b);
        tie(x, x2) = make_tuple(x2, x-x2 * q);
        tie(y, y2) = make_tuple(y2, y-y2 * q);
    }
    return a;
}

int main(){
	int x,y;
	cout << exgcd(84,30,x,y) << endl;
	cout << x << " " << y << endl;
	return 0;
}

Python:

def exgcd(a,b):
    x1, y1 = 1, 0
    x2, y2 = 0, 1
    while b!=0:
        q = a // b
        a, b = b, a % b
        x1, x2 = x2, x1 - x2 * q
        y1, y2 = y2, y1 - y2 * q
    return a, x1, y1

到目前为止，我们已经知道了如何求解

ax+by=gcd(a,b)

中的贝祖系数 $x,y$ ，接下来回到最开始的问题，求解方程

ax+by=c

聪明的你一定知道怎么求了，我们来看看代码

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int& x, int& y){
    x = 1; y = 0;
    int x2 = 0; int y2 = 1;
    while (b != 0){
        int q = a / b;
        tie(a, b) = make_tuple(b, a % b);
        tie(x, x2) = make_tuple(x2, x-x2 * q);
        tie(y, y2) = make_tuple(y2, y-y2 * q);
    }
    return a;
}

void solve(int a, int b, int c, int& x,int& y){
	int d = exgcd(a,b,x,y);
	if (c % d != 0) return;  // 无解
	x *= c / d; y *= c / d;
}

int main(){
	int x,y;
	solve(84,30,12,x,y);
	cout << x << " " << y << endl;
	return 0;
}

Python:

def solve(a,b,c):
    d, x, y = exgcd(a,b)
    if c % d != 0:
        return -1  # 无解
    return x * c // d, y * c // d

恭喜你，已经学会了使用 扩展欧几里得算法 计算贝祖系数和求解线性方程！

事实上，这个函数还有更简洁的写法，来看看代码

C++：

#include <tuple>
tuple<int, int, int> exgcd(int a, int b) {
    if (b == 0) return {a, 1, 0}; // 返回{gcd, x, y}
    auto [g, x1, y1] = exgcd(b, a % b);
    int x = y1;
    int y = x1 - (a / b) * y1;
    return {g, x, y};
}

Python:

def exgcd(a, b):
    if b == 0:
        return (a, 1, 0)  # (gcd, x, y)
    g, x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return (g, x, y)