零、概述

由于高中学习算法时对数论这个领域的抽象概念十分难以接受，所以基本没有学习多少数论知识，近日在哔哩哔哩大学看到一个相关的视频，于是便重新开始学习。本文算是对高中没学的知识的一个补充。
若没有特别说明，本文所有字母均代表整数

一、裴蜀定理又称贝祖定理(Bézout’s lemma)

${a},{b}$ 为不全为零的整数，则且 $gcd(a,b)=d$ ，则对于任意整数 $x,y$ ， $ax+by$ 都一定是 $d$ 的倍数。特别地，一定存在整数 $x,y$ ，使得 $ax+by=d$ 成立。

由于裴蜀定理的证明十分枯燥且难懂，证明略。
裴蜀定理的意义在于，对于一个不定方程 $ax+by=c$ ，该方程有解当且仅当 $c$ 为 $gcd(a,b)$ 的倍数。
对于一个像我这样的数论小白来说，裴蜀定理也许是个拗口又陌生的名字，但实际上，裴蜀定理是数论这个领域的基石（听别人说的）。

二、同余

从小学学习除法时，我们就学过这样的式子：

{14} \div {4} =3 \cdots 2

虽然在中学以及之后的学习中，我们总是希望能把被除数除净，于是引入了小数和分数的概念，但是，在数论中，我们关注更多的是余数。上式通常写成以下形式：

14 \equiv 2\quad \left(mod \quad 4 \right)

更一般地，有

a \equiv b\quad \left(mod \quad p \right)

特别地，若b=0，则可以记为

p|a

该式子有不同读法，一般为"a与b在模p意义下同余"，该式在数论中非常常见。
可以想象一下时钟这个例子，在时钟上只有1~12这12个整数，也就是模为12，而不论是1点还是13点亦或是25点（如果有的话），在时钟上表示的结果都为1点。

同余方程

同余方程的概念其实较为广泛，其实就是在模p意义下的方程，讨论比较广泛的是一次的同余方程，接下来会介绍一个简单的算法用于求解一次同余方程。

同余的封闭性
同余的恒等符号与等号十分相似，使人不难联想同余与等号是否有相似的性质。实际上，同余与等号有以下相同的性质：

若 ${a}_{1} \equiv {b}_1 (mod \quad p)$ 且 ${a}_{2} \equiv {b}_2 (mod \quad p)$ ，那么下式也成立： $a_1a_2 \equiv b_1b_2(mod \quad p)$ $a_1\pm a_2 \equiv b_1\pm b_2(mod \quad p)$ 即满足加减法和乘法的封闭性。
若 $a+c \equiv b(mod \quad p)$ 成立，那么 $a\equiv b-c(mod \quad p)$ 也成立。

需要格外注意的是，同余对除法并没有封闭性，于是就引出了除法逆元的概念。

三、乘法逆元

对于满足

a*b \equiv 1 \quad (mod \quad p)

的整数 $b$ ，我们称 $b$ 为 $a$ 在模 $p$ 意义下的乘法逆元，记作 $inv(a)=b$ 或 $a^{-1}=b(mod\quad p)$ ，需要注意的是，一个数在不同模意义下的乘法逆元通常不同。

乘法逆元有着与倒数十分相似的性质，所以我更喜欢称之为数论倒数。乘法逆元的意义在于，当我们在模p意义下希望计算除法时，我们可以直接乘以除数的乘法逆元（就好像除以一个数等于乘以这个数的倒数一样）

乘法逆元存在定理

乘法逆元存在的条件是a与模数互质。

该定理可以简单证明，若一个数a的逆元存在，则可以表示为

a*inv(a)+p*k=1

由裴蜀定理可知，p和a的公约数必须能整除1，即两数必须互质。

乘法逆元的求解

要得到一个数在模p意义下的乘法逆元，可以用费马小定理（前提是p为质数）

费马小定理：
$a^{p-1} \equiv 1(mod \quad p)$

根据费马小定理，有 $a*a^{p-2} \equiv1(mod \quad p)$ ，所以 $a^{p-2}$ 为 $a$ 在模p意义下的乘法逆元。
但是，该算法有较多的局限性，一般情况下，通常用扩展欧几里得算法求解乘法逆元。

四、扩展欧几里得算法

扩展欧几里得算法通常用于求解不定方程 $ax+by=d$ 的（也就是一次同余方程 $ax\equiv d(mod\quad b)$ ），为什么叫做扩展欧几里得算法？就是因为该算法是由欧几里得算法扩展出来的。这里先重温一下欧几里得算法的内容：

$gcd(a,b)=gcd(b,a\%b)$

这个算法在高中就学过了，这里证明略。
接下来是扩展欧几里得算法解不定方程的推导过程：
由裴蜀定理，不定方程中的 $d$ 必须为 $gcd(a,b)$ 的整数倍,为了简便，我们只计算方程 $ax+by=gcd(a,b)$ 的解，其他情况下的解可以通过倍乘该方程的解来求出。
为简便，我们设 $g=gcd(a,b)$
观察欧几里得算法发现，该算法停止的条件为a=g,b=0，则此时方程可以写为：

g*1+0*y=g

我们可以试图该状态逆推回，即代入欧几里得算法的条件

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

我们可以得到

gcd(a,b) =gcd(b,a\%b) = gcd(b,a-\lfloor{\frac{a}{b}}\rfloor*b)

即：

ax+by=g=b*x^{\prime} + (a-\lfloor{\frac{a}{b}}\rfloor*b)*y^{\prime}=a*y^{\prime}+b*(x^{\prime}-\lfloor{\frac{a}{b}}\rfloor*y)

对比左右两个式子可以发现,当我们已经获得“更深一层递归”中的 $x^{\prime}$ 和 $y^{\prime}$ 时，我们可以得出x和y：

\begin{cases} x=y'\\ y=x'-\lfloor\frac{a}{b}\rfloor*y \end{cases}

所以，当我们利用欧几里得算法计算最大公约数时，我们可以“顺便”递推求出上面这个不定方程的解。
扩展欧几里得算法的C\C++ 代码实现如下：

typedef long long LL;
//注意，后两个参数使用的是引用
LL exgcd(LL a,LL b,LL &x,LL &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	LL d=exgcd(b,a%b,x,y);
	LL temp=x;
	x=y;
	y=temp-a/b*y;
	return d;
}

不难发现，实际上我们需要求解的方程是有无数多组解的，而我们只求出来其中的一组解，我们可以称之为特解，而想要求出通解，可以通过以下方法：
首先，我们设通过此算法求出的特解为 $x_0,y_0$ ,将其代入不定方程，设整数k，做如下变换：

a(x_0+kb)+b(y_0-ka)=g

不难发现，该式与原方程是等价的，于是该方程的解可以扩展为

\begin{cases} x=x_0+kb\\ y=y_0-ka \end{cases}

实际上，这样的解并不能包含全部的解，我们并不需要设这样一个“整数”k，只需要满足 $kb$ 和 $ka$ 均为整数即可，我们可以将k的条件扩大，变为：

a(x_0+\frac{k}{g}*b)+b(y_0-\frac{k}{g}*a)=g

所以，最终的解系为：

\begin{cases} x=x_0+\frac{k}{g}*b\\ y=y_0-\frac{k}{g}*a \end{cases}

利用这样的一个解系，可以求出满足不定方程的所有解，大部分问题会要求算出满足的x中的最小值，则可以利用该式求出。
对于不定方程右边不为 $gcd(a,b)$ 的情况（但必须是gcd的t倍），只需要将解系中的x和y也乘以t即可

利扩展用欧几里得算法求解乘法逆元

乘法逆元的定义为

a*inv(a)\equiv1(mod\quad p)

则我们设一个整数k，该式可以表达为

a*inv(a)+p*k=1

则该方程其实就是一次同余方程的一种存在形式，前提是a和p互质，利用扩展欧几里得算法可以轻松求出。

数论基础

零、概述

一、裴蜀定理又称贝祖定理(Bézout’s lemma)

二、同余

同余方程

三、乘法逆元

乘法逆元存在定理

乘法逆元的求解

四、扩展欧几里得算法

利扩展用欧几里得算法求解乘法逆元

更多方程？

数论基础

零、概述

一、裴蜀定理 又称贝祖定理(Bézout’s lemma)

二、同余

同余方程

三、乘法逆元

乘法逆元存在定理

乘法逆元的求解

四、扩展欧几里得算法

利扩展用欧几里得算法求解乘法逆元

更多方程？

一、裴蜀定理又称贝祖定理(Bézout’s lemma)