0x00 前提知识

同余

$\equiv$：是数论中表示同余的符号。
用法：$a \equiv b \pmod n$

定义

• 最基本的定义：两个数$a,b$对另一个数$n$的取余都相同。
• 衍生定义：$(a-b) \bmod n = 0$

记作：$a \equiv b \pmod n$，表示$a,b$对$n$同余。

如：
$7 \bmod 3 = 1$
$10 \bmod 3 = 1$
则：$7 \equiv 10 \pmod 3$

性质

以下部分为个人总结，名称不一定准确。

1. 自反性：$a \equiv a \pmod m$。
2. 对称性：若$a \equiv b \pmod m$，则$b \equiv a \pmod m$。
3. 传递性：若$a \equiv b \pmod m$，$b \equiv c \pmod m$，则$a \equiv c \pmod m$。
4. 替换性：对于$M \equiv ab \cdot x \pmod m$，若$ab \equiv c \pmod m$，则$M \equiv c \cdot x\pmod m$。
5. 加减可移项性：若$a \pm b \equiv c \pmod m$，则$a \equiv c \mp b \pmod m$
6. 线性运算：如果$a \equiv b \pmod m$，$c \equiv d \pmod m$，那么有：
   1. $a \pm c \equiv b \pm d \pmod m$。
   2. $ac \equiv bd \pmod m$。
      推论：若$a \equiv b \pmod m$，则有$an \equiv bn \pmod m (n\in Z, n \ne 0)$。
7. 模数的除法：若$ac \equiv bc \pmod m$，$\gcd(m,c)=d$，则$a \equiv b \pmod{m/d}$；
   特别地，当$\gcd(m,c)=1$时，有$a \equiv b \pmod m$。
8. 模数的乘法：若$a \equiv b \pmod m$，则有$ak \equiv bk \pmod{mk}$，其中$k$为大于零的整数；
   推论：若$a \equiv b \pmod m$，$d$为$a,b$及$m$三者的任一正公约数，则$a/d \equiv b/d \pmod{m/d}$。
9. 传递性2：若$a \equiv b \pmod m$，且$d \mid m$，则$a \equiv b \pmod d$。

参考自“wcwcwch”的「同余的性质」。

其他点

需要注意的是：
负数也可以进行取模，因此也存在同余。

如：
$-36 \bmod 15$，
用除法表示为$-36 \div 15 = -3 \cdots 9$（验算：$15*-3+9=-36$），
即$-36 \bmod 15 = 9$，

所以$-36 \equiv 24 \pmod{15}$。

由于这个符号很新颖和陌生，导致在学习的时候理解上产生了很大的障碍，
因此需要尽快适应这个符号的使用方法。

首先需要知道的是：同余代表的是一种关系，而非运算。
因此才会采用类似于等号的符号来表示。
但这种等于，并不是像$2=2$这样直接就可以判断，
而是要经过稍微的运算，两边同时取模后等于，才叫同余。

然后对于这个符号，有很多种不同的理解方式，
建议自己确定一个自己习惯的理解方式并一直用下去。
个人所采用的是：$a \equiv b \pmod m$，代表$a \bmod m = b \bmod m$。

需要牢记一个转换式： $$ a \equiv b \pmod m \implies a = mk + b (k∈Z) $$

整除

$\mid$：是数论中的表示整除符号。
用法：$a \mid d$

注意：
这里的整除就是整除，不是被整除。
如上例：是$a$整除$b$，或说$b$被$a$整除。

如：
$2\mid14$
则是$2$整除$14$，$14$被$2$整除。

整除也代表两者大除小余数为$0$，故同余还可以写为：
$m \mid (a-b)$
$\implies (a-b) \bmod n = 0$
$\implies a \equiv b \pmod n$

学习顺序

1. 裴蜀定理
2. 扩展欧几里得
3. 初步认识线性同余方程
4. 认识乘法逆元并求解
5. 求解线性同余方程

其中：

• 1、2为$\gcd$内容，
• 3、4、5为本章（线性同余方程）内容。

0x01 初步认识

定义

形如$f(x) \equiv 0 \pmod m$的方程称为同余方程，
其中$f(x)=a_nx^n+a_{n-1}x^{n_1}+\cdots+a_1x+a_0$。

记：$f(x)$最高次数为$n$，则称为$n$次同余方程。
特别的：当$n=1$时，称为一次同余方程，又称线性同余方程。

即：
形如$ax \equiv b \pmod m$的方程，
被称为线性同余方程(Congruence Equation)。

如：
$12x \equiv 9 \pmod {15}$
解得：$x=\cdots,-3,2,7,12,17,\cdots,5n+2(n∈Z)$

当$x=-3$时，$12*-3=36$，$-36 \bmod 15 = 9$，满足方程。
当$x=2$时，$122=24$，$24 \bmod 15 = 9$，满足方程。
当$x=7$时，$127=84$，$84 \bmod 15 = 9$，满足方程。

同样，对于这个方程，
我们也需要对其快速建立自己的理解方法。

个人理解方法是：
当$x$取某一值时，则$ax$对$m$取模的结果就是$b$。

与普通的一元线性方程不同的是：
普通的一元线性方程肯定存在唯一解（如$2x+3=5$）；
而线性同余方程若有解，需要存在一定条件。

有解条件

对于线性同余方程$ax \equiv b \pmod m$，其存在解的条件是：
$b$能够被$a$与$m$的最大公约数整除。

表示为： $$ \gcd(a,m) \mid b $$

如上例中：
$12x \equiv 9 \pmod {15}$

因为$\gcd(12,15)=3$，而$3$能整除$9$，
即$\gcd(12,15) \mid 9$，
所以有解。

如：
$3x \equiv 5 \pmod 6$，

因为$\gcd(3,6)=3$，而$3$不能整除$5$，
故该同余方程无解，
也就是说无论你$x$取何值，都不能满足$3x$对$6$取模后值为$5$。

注意到，若$x_0$是线性同余方程$ax \equiv b \pmod m$的一个解，
那么对于$x_n \equiv x_0 \pmod m$，$x_n$也是该线性同余方程的解。
或者说$mk+x_0(k∈Z)$均为解。

如上例中：
$12x \equiv 9 \pmod {15}$

$x_0=2$时为一解，
因此$15k+2(k∈Z)$均为解，即$2,17,32,\cdots$均为解。

$x_0=7$时为一解，
因此$15k+7(k∈Z)$均为解，即$7,22,37,\cdots$均为解。

$x_0=12$时为一解，
因此$15k+12(k∈Z)$均为解，即$12,27,42,\cdots$均为解。

因此对于线性同余方程的解的个数，我们定义为：
在$0 \sim (m-1)$中解的个数。

如上例中：
$12x \equiv 9 \pmod {15}$

解的个数就为$3$个，分别为$2,7,12$。

解的性质

对于线性同余方程$ax \equiv b \pmod m$，记$\gcd(a,m)=d$
若存在解，则会满足以下性质：

1. 对于$x_0$为该线性同余方程的任意一解，记，
   则通解可以表示为$\frac{m}{d}k + x_0 (k∈Z)$。

   如上例中：
   $12x \equiv 9 \pmod {15}$
   $d=\gcd(12,15)=3$

   得到一解$x_0=2$，
   则通解可以表示为$5k+2(k∈Z)$。

2. 解的个数恰为$d$个。

   如上例中：
   $12x \equiv 9 \pmod {15}$

   则在$0 \sim 14$范围中，解为$2,7,12$。
   个数为$d=\gcd(12,15)=3$，即$3$个。

3. 唯一解定理：
   当$d=1$时，该同余方程有且仅有唯一解。

0x02 乘法逆元

定义

如果一个线性同余方程$ax \equiv 1 \pmod m$，存在解$x$，
则$x$称为$a \bmod m$的逆元，记作$a^{-1}$。

如：
$5x \equiv 1 \pmod{14}$，

当$x=3$时，$15 \bmod 14 = 1$，满足方程。
所以$3$为$5$关于$14$的逆元。

性质

对于一个线性同余方程$ax \equiv 1 \pmod m$，
记$a$关于$m$的逆元$x$为$a^{-1}$。

1. 存在充要条件：$a,m$互素，$\gcd(a,m)=1$。
2. 唯一性：$a^{-1}$在$[0,m-1]$范围内唯一。

   证明：

   我们先假设$a$有两个不相等逆元：$a’$ 和$a’’$，
   那么一定有：$aa’ \equiv aa’’ \equiv 1 \pmod m$

   不妨设$a’∈[0,m-1]$，$a’<a’’$且$a’’-a’=k$，
   那么由于$a\ne0$，所以$k$一定是$k \equiv 0 \pmod m$ ，即$k=cm(c∈Z,c\ne0)$（见最上的转换式）
   所以$a’’=a’ + cm(c∈Z,c\ne0)$，
   所以$a’‘∈[cm,(c+1)m-1] (c∈Z,c\ne0)$，一定不在$[0,m-1]$范围内，
   所以$a$在$[0,m-1]$范围内只能有一个逆元。

3. 完全积性：$a^{-1} \cdot b^{-1} = (a \cdot b)^{-1}$
4. $\gcd(a^{-1},m)=1$。
5. ${(a^{-1})}^{-1} \equiv a \pmod m$

作用

1. 对除法取模

首先对于取模运算，存在以下性质：
$(a + b) \bmod p = ((a\bmod p) + (b\bmod p)) \bmod p$ （对）
$(a - b) \bmod p = ((a\bmod p) - (b\bmod p)) \bmod p$ （对）
$(a \times b) \bmod p = ((a\bmod p) \times (b\bmod p)) \bmod p$ （对）

$(a \div b) \bmod p = ((a\bmod p) \div (b\bmod p)) \bmod p$ （错）

如：
$(100/50)\bmod20 = 2$
$\nRightarrow((100\bmod20)/(50\bmod20))\bmod20=0$

因此如果对于一些题目，如果运算要求求余，但该运算为除法，
我们就不能直接像加减乘运算一样拆开求余。

但如果被除数，除数也超范围，那是不是只能用高精度了？
并不是这样，我们可以利用乘法逆元来拆开求余。

乘法逆元又称为数论倒数。
既然这么称呼，那么乘法逆元就跟倒数有相似之处。

对于普通的数学运算$a \div b$，
其也可以写成$a \times \frac{1}{b}$。

因此对于求余运算$(a/b) \bmod m$，
其也可以写成$(a \cdot b^{-1}) \bmod m$，

这时便可以拆开求余为$((a\bmod m) \cdot (b^{-1}\bmod m))\bmod m$。

即存在性质： $$ a/b \bmod m = a \cdot b^{-1} \bmod m $$

参考自“Aloof__”的「乘法逆元的作用（逆元的作用是什么）」。

证明

根据逆元的定义，存在： $$ b \cdot b^{-1} \equiv 1 \pmod m $$

同余式两边同乘$a$，得到： $$ ab \cdot b^{-1} \equiv a \pmod m $$

同余式两边同除$b$，得到： $$ a \cdot b^{-1} \equiv a/b \pmod m $$

得证。

2. 线性同余方程的反函数

对于线性同余方程$ax \equiv b \pmod m$，
表示为函数的形式即为$f(x) = ax \bmod m$。

如果知道函数值$f(x)$，
那么反求解$x$的方法为：$x = f(x) \cdot a^{-1}$。

需要满足$x<m$，
否则为$x \equiv f(x) \cdot a^{-1} \pmod m$。

如：
$2x \equiv f(x) \pmod{11}$。 当$x = 13$时，$f(x) = 4。

$2$对$11$的逆元是$6$，
$4 \times 6 = 24$。

$24 \equiv x(13) \pmod{11}$，
而不是$24 = x(13)$。

主要应用于CTF中仿射加密的解密。

证明

很简单的证明。

$$ ax \equiv f(x) \pmod m $$

$$ ax \cdot a^{-1} \equiv f(x) \cdot a^{-1} \pmod m $$

$$ x \equiv f(x) \cdot a^{-1} \pmod m $$ 得证。

求解方法

待补充！……