浅谈初等数论

· · 算法·理论

组合数学

排列组合

【定义】

从 n 个不同元素中，有序地取出任意 k 个元素排成一列，称之为取出一个排列能取出的所有排列个数称为排列数，用符号 P_n^k 或 A_n^k 表示。

A_n^k=n(n-1)(n-2)\cdots(n-k+1)=\frac{n!}{(n-k)!}

从 n 个不同元素中，任取 k 个元素组成一个集合，称之为取出一个组合能取出的所有组合个数称为组合数，用符号 \binom{n}{k} 表示。

\binom{n}{k}=\frac{A_n^k}{k!}=\frac{n!}{k!(n-k)!}

P8692 [蓝桥杯 2019 国 C] 数正方形（加强版）

:::info[题目描述]{open} 增强版与原题不一样的是，题目中是 N^2 的点阵，但此处是矩阵。另外，数据增强到 1\leq N\leq 10^9。 ::: :::success[如何求解]{open} 设最后的最多答案位 \operatorname{ans}，则有下面的推论。

\begin{aligned} \operatorname{ans}&=\sum_{i=1}^n(n-i+1)^2i\\ &=\sum_{i=1}^ni^2(n-i+1)\\ &=(n+1)\Bigg(\sum_{i=1}^ni^2\Bigg)-\Bigg(\sum_{i=1}^ni^3\Bigg)\\ &=(n+1)\Bigg[\frac{n(n+1)(2n+1)}6\Bigg]-\Bigg[\frac{n(n+1)}2\Bigg]^2 \end{aligned}

:::

二项式定理

【定理】

设 a,b\in\mathbb R 且 n\in\mathbb Z，则

(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k

特别地，当 a=b=1 时，有

\sum_{k=0}^n\binom{n}{k}=2^n

【扩展】卡特兰数

对于 n\in\mathbb Z，卡特兰数满足以下的递推关系。

C_n= \begin{cases} 1\quad&\text{if\ \,}n=0\\ \sum_{i=0}^{n-1}\quad&\text{if\ \,}n>0 \end{cases}

【例题】P1641 [SCOI2010] 生成字符串

:::info[题目描述]{open} 你需要生成一个正好包含 n 个 \texttt 1 和 m 个 \texttt 0 的 \texttt{0/1} 串，对于你生成的 \texttt{0/1} 串，它的任意前缀还要满足 \texttt 1 的数量不少于 \texttt 0 的数量；求方案数，答案对大质数取模。数据满足 1\leq m\leq n\leq 10^6。 ::: :::success[如何求解]{open} 使用卡特兰数完成此题目（实际上就是求广义卡特兰数）。

不难计算出（设最终答案位 \text{ans}）以下答案。

\text{ans}=\binom{n+m}n-\binom{n+m}{m-1}

:::

容斥原理

【定理】

假设 U 中的元素有 n 种不同属性，拥有第 i 种属性的元素集合为 S_i，则

\sum_{i<j<k}|S_i\cap S_j\cap S_k|+\cdots+(-1)^{n-1}|S_1\cap S_2\cap\cdots\cap S_n|

【例题】P1450 [HAOI2008] 硬币购物

:::info[题目描述]{open} 共有 4 种硬币。面值分别为 c_1,c_2,c_3,c_4。

某人去商店买东西，去了 n 次，对于每次购买，他带了 d_i 枚 i 种硬币，想购买 s 的价值的东西。请问每次有多少种付款方法。
:::success[如何求解]{open}
可以先考虑硬币没有数量限制的情况，使用完全背包，对于询问价值 s，返回 f[s]；

再考虑只有一种硬币有限制（例如硬币 c_1 最多能使用 d_1 枚），对于询问价值 s，返回 f[s]-f[s-c_1(d_1+1)]，也就是所有方案数减去至少用了 d_1+1 枚 c_1 的方案数；

类似的，如果只有硬币 c_1,c_3 有限制也可以解出来。

最后总共 16 种方案全算出来，再用容斥原理拼凑出最终答案。
### 数论分块
#### 【定义】
数论分块可以快速计算一些形如
\sum_{i=1}^nf(i)g\Big(\Big\lfloor\frac{n}{i}\Big\rfloor\Big)
的的和式。如果可以在 \mathcal O(1) 的时间内计算出 \sum_{i=l}^rf(i) 或已经预处理出 f 的前缀和时，数论分块就可以在 \mathcal O(\sqrt n) 的时间内计算出上面的和式。
#### 【例题】整数分块
:::info[题目描述]{open}
对于（100\% 数据的）n\in\mathbb Z，计算下面的式子。
\sum_{i=1}^n\Big\lfloor\frac n i\Big\rfloor
:::
:::success[如何求解]{open}
我们可以计算下面这个式子。
$$
\begin{aligned}
q&=\Big\lfloor\frac n L\Big\rfloor\
\text{ans}&=\sum_{L=1}^{n}\Big[q\times\Big(\Big\lfloor\frac n q\Big\rfloor-L+1\Big)\Big]
\end{aligned}
$$
然后下面是模拟计算的伪代码。
```cpp line-numbers
typedef long long LL;

LL floor_sum(LL n){ LL ans=0; for(LL L=1,R;L<=n;L=R+1){ LL q=n/L; R=n/q; ans+=q*(R-L+1); } return ans; }

:::
#### 【例题】P2261 [CQOI2007] 余数求和
:::info[题目描述]{open}
给出正整数 $n$ 和 $k$，请计算

$$G(n, k) = \sum_{i = 1}^n k \bmod i$$

其中 $k\bmod i$ 表示 $k$ 除以 $i$ 的余数。
:::
:::success[如何求解]{open}
通过计算下面这个式子可以得到答案。
$$\begin{aligned}\sum_{i = 1}^n k \bmod i&=\sum_{i=1}^nk-i\Big\lfloor\frac k i\Big\rfloor\\&=nk-\sum_{i=1}^ni\Big\lfloor\frac k i\Big\rfloor\end{aligned}$$
本题目是一道 **【模板题】**，话不多说，直接开写。（代码由 @[Furina_oier](https://www.luogu.com.cn/user/1399773) 提供）
```cpp line-numbers
#include<bits/stdc++.h>
using namespace std;

// 省略快读快写

signed main(){
    int n=read(),k=read();
    int ans=n*k;
    for(int i=1,j;i<=n;i=j+1){
        if(k/i!=0)
        j=min(k/(k/i),n);
        else j=n;
        ans-=(k/i)*(j-i+1)*(l+r)/2;
    }
    write(ans,0);
    return 0;
}

:::

矩阵乘法

【定义】

首先我们需要了解什么是矩阵。对于 m,n\in\mathbb Z^+,a_{ij}\in\mathbb Z，下面就是矩阵。

\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}

那么，对于下面两个矩阵

\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}, \begin{bmatrix} b_{11} & b_{12} & \cdots & b_{1p} \\ b_{21} & b_{22} & \cdots & b_{2p} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \cdots & b_{np} \end{bmatrix}

其乘积为

\begin{bmatrix} \sum\limits_{k=1}^{n} a_{1k}b_{k1} & \sum\limits_{k=1}^{n} a_{1k}b_{k2} & \cdots & \sum\limits_{k=1}^{n} a_{1k}b_{kp} \\ \sum\limits_{k=1}^{n} a_{2k}b_{k1} & \sum\limits_{k=1}^{n} a_{2k}b_{k2} & \cdots & \sum\limits_{k=1}^{n} a_{2k}b_{kp} \\ \vdots & \vdots & \ddots & \vdots \\ \sum\limits_{k=1}^{n} a_{mk}b_{k1} & \sum\limits_{k=1}^{n} a_{mk}b_{k2} & \cdots & \sum\limits_{k=1}^{n} a_{mk}b_{kp} \end{bmatrix}

简单地，有公式

c_{ij} = \sum_{k=1}^{n} a_{ik} \, b_{kj}

而且，矩阵乘法满足结合律（不一定满足交换律）。

【扩展】矩阵加法

矩阵加法比矩阵乘法简单，只需要按位相加即可。

【例题】台阶问题（加强版）

:::info[题目描述]{open} 有 N 级台阶，你一开始在底部，你一脚能迈 1 到 K 级台阶，问走完全部台阶有多少种不同方式，答案对 10^5+3 取模。对于 100\% 的数据，满足 1\leq N\leq 10^{18},1\leq K\leq 10^2。

本题目为加强版，原题数据范围 1\leq N\leq 10^5,q\leq K\leq 10^2。
:::success[如何解决]{open}
下面有多种做法，区别就在于时间复杂度。

OI 中，无特殊说明，约数 \in\mathbb Z^+（事实上，整个 OI 数论都默认不讨论负数）。

【基本性质】

设 a,b,c\in\mathbb Z，且 a\neq 0。

此外，还有四舍五入函数，但是数论中并不常用（值得注意的是，当 x\leq 0 时，计算 \lfloor x\rceil 容易出错；如 \lfloor -2.5\rceil=-3）。

\lfloor x\rceil= \begin{cases} \lfloor x+0.5\rfloor\quad&\text{if\ \,}x\geq0\\ \lceil x-0.5\rceil\quad&\text{if\ \,}x<0 \end{cases}

【基本性质】

设 x,y\in\mathbb R 且 n\in\mathbb Z。

则称 d 为 a_1,a_2,\cdots,a_n 的最大公约数，记作下面这个式子。

d=\gcd(a_1,a_2,\cdots,a_n)

也可以写作下面这个式子。

d=(a_1,a_2,\cdots,a_n)

【定义】最小公倍数

设 a_1,a_2,\cdots,a_n 是 n 个非零的整数，如果正整数 m 满足以下条件。

则称 m 为 a_1,a_2,\cdots,a_n 的最小公倍数，记作下面这个式子。

m=\text{lcm}(a_1,a_2,\cdots,a_n)

也可以写作下面这个式子。

m=[a_1,a_2,\cdots,a_n]

【基本性质】

接下来考虑，每个红色数字意味着这一行它左边的金额都无法支付，右边都能支付；换句话说每个红色数字 A 对应着 \big\lfloor\frac A p\big\rfloor 个灰色数字，且其中最大的是 A-p，故灰色数字共有 \sum_{i=1}^{p-1}\big\lfloor\frac {iq} p \big\rfloor 个，最大的灰色数字为 (p-1)q-p。

最大价格找出来了，接下来求下面这个式子的值。

f(p,q)=\sum_{i=1}^{p-1}\Big\lfloor\frac{iq} p\Big\rfloor

那我们来求一下。

容易知道 n=\sum_{i=1}^{+\infty}\llbracket i\leq n\rrbracket，还有当 a,b,c\in\mathbb Z^+ 时，\llbracket a\leq \big\lfloor\frac bc\big\rfloor\rrbracket=\llbracket a\leq \frac bc\rrbracket=\llbracket ac\leq b\rrbracket。

下面我们推算。

\begin{aligned} f(p,q) &= \sum_{i=1}^{p-1} \left\lfloor \frac{iq}{p} \right\rfloor\\ &= \sum_{i=1}^{p-1} \sum_{j=1}^{q-1} \left[\!\left[ j \le \left\lfloor \frac{iq}{p} \right\rfloor \right]\!\right] \\ &= \sum_{i=1}^{p-1} \sum_{j=1}^{q-1} \left[\!\left[ jp \le iq \right]\!\right] \\ &= (p-1)(q-1) - \sum_{j=1}^{q-1} \sum_{i=1}^{p-1} \left[\!\left[ iq < jp \right]\!\right] \\ &= (p-1)(q-1) - \sum_{j=1}^{q-1} \sum_{i=1}^{p-1} \left[\!\left[ i < \frac{jp}{q} \right]\!\right] \\ &= (p-1)(q-1) - \sum_{j=1}^{q-1} \sum_{i=1}^{p-1} \left[\!\left[ i < \left\lfloor \frac{jp}{q} \right\rfloor \right]\!\right] \end{aligned}

因为 p\perp q，所以 \frac{jp}q 是整数当且仅当 \frac j p 是整数，又因为 j<q，所以不为，故有下面的式子。

\begin{aligned} f(p,q) &= \sum_{i=1}^{p-1} \left\lfloor \frac{iq}{p} \right\rfloor\\ &= (p-1)(q-1) - \sum_{j=1}^{q-1} \sum_{i=1}^{p-1} \left[\!\left[ i < \left\lfloor \frac{jp}{q} \right\rfloor \right]\!\right] \\ &= (p-1)(q-1) - \sum_{j=1}^{q-1} \left\lfloor \frac{jp}{q} \right\rfloor \\ &= (p-1)(q-1) - f(q,p) \end{aligned}
综上，f(p,q) + f(q,p) = (p - 1)(q - 1)，所以答案为 \frac{(p-1)(q-1)}{2}。
### 素数
#### 【定义】
设 p\in\mathbb Z^+ 并且 p>1，若 p 的正因数只有 1 和 p 本身，则称 p 为素数（或质数）。否则，称 p 为合数。
\mathbb P=\{p\in\mathbb Z^+\mid p>1 \displaystyle{\texttt{ 且 }} p\displaystyle{\texttt{ 是素数}}\}
特别地，1 既不是素数也不是合数。
#### 【基本性质】
- 整除性：若 p \nmid a ，则 \gcd(p,a) = 1 ；
- 整除性推广：若 p \mid a_1 a_2 \dots a_n ，则存在某个 i 使得 p \mid a_i ；
- 素性判定：若对所有满足 1 < d \leq \sqrt{p} 的整数 d 都有 d \nmid p ，则 p 是素数；
- 素数的个数：素数个数是无限的（欧几里得证明）；
- 标准分解式：任意大于 1 的整数 n 都可以唯一地（不考虑顺序）表示为下面这个式子。
$$
n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}
$$
其中 p_1 < p_2 < \dots < p_k 是素数， \alpha_i \in \mathbb{N}^* ，这也称之为 n 的质因数分解 。
## 同余方程与中国剩余定理
### 同余
#### 【定义】
设 m\in\mathbb Z^+，若 a,b\in\mathbb Z 满足 m\mid (a-b)，则称 a 与 b 模 m 同余，记作下面这个式子。
a\equiv b\pmod m
此时 m 称为模数（或模），该式称为同余式；若 m\nmid (a-b)，则称 a 与 b 模 m 不同余，记作下面这个式子。
a\not\equiv b\pmod m
#### 【基本性质】
设 a,b,c,d \in \mathbb{Z} ， m \in \mathbb{Z}^+。
- 自反性： a \equiv a \pmod{m} ；
- 对称性：若 a \equiv b \pmod{m} ，则 b \equiv a \pmod{m} ；
- 传递性：若 a \equiv b \pmod{m} 且 b \equiv c \pmod{m} ，则 a \equiv c \pmod{m} ；
- 保加性：若 a \equiv b \pmod{m} 且 c \equiv d \pmod{m} ，则 a + c \equiv b + d \pmod{m} ；
- 保乘性：若 a \equiv b \pmod{m} 且 c \equiv d \pmod{m} ，则 ac \equiv bd \pmod{m} ；
- 幂等性：若 a \equiv b \pmod{m} ，则对任意 n \in \mathbb{N}^* ，有 a^n \equiv b^n \pmod{m} ；
- 消去律：若 ac \equiv bc \pmod{m} 且 \gcd(c, m) = 1 ，则 a \equiv b \pmod{m} ；
- 与带余除法的关系： a \equiv b \pmod{m} 当且仅当 a 和 b 除以 m 所得余数相同。
### 裴蜀定理
#### 【定理】
设 a,b 是不全为零的整数，则存在整数 x,y，使得
ax+by=\gcd(a,b)
特别地，a 与 b 互素当且仅当存在整数 x,y 满足 ax+by=1。
#### 【扩展】扩展欧几里得算法
:::info[题目描述]{open}
输入两个不同时为 0 的整数 a,b；

输出 g,x,y，满足下面这个式子。

ax+by=g=\gcd(a,b)

::: :::success[解法和证明]{open}

auto ExEuclid(auto a,auto b){
    if(b==0)return abs(a),sign(a),0;
    auto x1,y1;
    x1=y1=g=ExEuclid(b,a%b);
    x=y1;
    y=x1-(a div b)*y1;
    return g,x,y;
}

上述是计算扩展欧几里得的算法伪代码（直接使用会导致编译错误）。

那我们如何证明？我们可以证明 a,b\geq 0 的情况，其他情况相类似可类比。再次提醒，代码中第 6 行中的 a div b 并不等价于数学公式中的 \big\lfloor\frac a b\big\rfloor。

\begin{aligned} &x_1b+y_1(a\bmod b)\\ =\,&x_1b+y_1\Big(a-\frac a b\Big)\\ =\,&y_1a+\Big(x_1-\frac a b y_1\Big) \end{aligned}

:::

二元一次不定方程 & 同余方程

【定义】二元一次不定方程

$$A\cdot x+B\cdot y=C$$ 关于 $x,y$ 的全体整数解。 #### 【定义】二元一次不定方程 $A,B,m$ 均为整数，求出方程 $$A\cdot x\equiv B\pmod m$$ 关于 $x$ 的全体整数解。 #### 【推论】两者等价 $$ \begin{aligned} A\cdot x+B\cdot y=C&\iff B\cdot y=C-A\cdot x\\ &\iff B\mid C-A\cdot x\\ &\iff A\cdot x\equiv C\pmod B \end{aligned} $$ #### 【例题】P2421[NOI2002] 荒岛野人 :::info[题目描述]{open} 克里特岛以野人群居而著称。岛上有排列成环形的 $m$ 个山洞。这些山洞顺时针编号为 $1,2,\dots ,m$。岛上住着 $n$ 个野人，一开始依次住在山洞 $C_1,C_2,\dots ,C_n$ 中，以后每年，第 $i$ 个野人会沿顺时针向前走 $P_i$ 个洞住下来。 每个野人 $i$ 有一个寿命值 $L_i$，即生存的年数。 下面四幅图描述了一个有 $6$ 个山洞，住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为 $1,2,3$；每年要走过的洞穴数依次为 $3,7,2$；寿命值依次为 $4,3,1$。 ::: :::success[如何求解]{open} 既然 $m$ 这么小，那肯定是枚举 $m$ 判断是否合法； 考虑野人 $i$ 和野人 $j$ 相遇的条件，即存在不超过 $\min(L_i, L_j)$ 的时间 $t$ 使得： $$ C_i + P_i t \equiv C_j + P_j t \pmod{m} $$ 整理得同余方程： $$ (P_i - P_j) t \equiv C_j - C_i \pmod{m} $$ 求出最小的非负整数解 $t_0$ 看看是人相遇还是骨灰相遇，小心爆 `int`，虽然本题的数据范围不会。 ::: ### 逆元 #### 【定义】 设 $a, m \in \mathbb{Z}$，若存在整数 $x$ 使得 $$ ax \equiv 1 \pmod{m} $$ 则称 $x$ 为 $a$ 模 $m$ 的 **逆元**（或模逆元），记作 $a^{-1} \pmod{m}$ 或 $a^{-1} \mod m$。 $$ aa^{-1} \equiv 1 \pmod{m} $$ 此时也称 $a$ 在模 $m$ 下 **可逆**（或存在逆元）。 若这样的 $x$ 不存在，则称 $a$ 在模 $m$ 下 **不可逆**。 #### 【性质】 设 $a, b, m \in \mathbb{Z}$。 - **存在性定理**: $a$ 模 $m$ 存在逆元当且仅当 $\gcd(a, m) = 1$； - **唯一性**: 若 $a$ 模 $m$ 的逆元存在，则它们模 $m$ 的余数相同； - **逆元的逆元**: 模 $m$ 意义下，若 $a$ 可逆则 $a^{-1}$ 也可逆，且 $(a^{-1})^{-1} \equiv a \pmod{m}$； - **乘积的逆元**: 若 $a$ 和 $b$ 均模 $m$ 可逆，则 $ab$ 也模 $m$ 可逆，且 $$ (ab)^{-1} \equiv b^{-1}a^{-1} \pmod{m} $$ - **除法定义**: 若 $b$ 在模 $m$ 下可逆，则定义 $$ \frac{a}{b} \equiv ab^{-1} \pmod{m} $$ ### 中国剩余定理 #### 【定义】 设 $m_1, m_2, \ldots, m_k$ 是两两互素的正整数，则对于任意整数 $a_1, a_2, \ldots, a_k$，同余方程组 $$ \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases} $$ 在模 $M = m_1,m_2,\ldots,m_k$ 的意义下有唯一解； 即 $[0, M-1]$ 内存在唯一的整数 $x$ 满足上述所有同余式。 #### 【证明】解在存 设 $ M_i = \prod_{j \neq i} m_j = \frac{M}{m_i} $，显然 $ \gcd(m_i, M_i) = 1

故存在整数 t_i 使得 M_i t_i \equiv 1 \pmod{m_i} ，即 t_i 是 M_i 模 m_i 的逆元构造

x_0 = \sum_{i=1}^k a_i M_i t_i

发现它是同余方程组的一个特解，即满足所有的

x_0 \equiv a_i \pmod{m_i}

【证明】解唯一

假设 x 和 y 都是同余方程组的解，即对所有 i 有

x \equiv y \equiv a_i \pmod{m_i}

即 m_i \mid (x - y) 对所有 i 成立，因此 \text{lcm}(m_1, m_2, \cdots, m_k) \mid (x - y)
考虑 m_1, m_2, \cdots, m_k 两两互素，\text{lcm}(m_1, m_2, \cdots, m_k) = M
因此同余方程的所有解模 M 的余数相同，故通解为

x \equiv x_0 \equiv \sum_{i=1}^k a_i M_i t_i \pmod{M}

\text{Lucas} 定理

【定理】

设 n, m, p \in \mathbb{Z}^+ 且 p 为素数，则

\binom{n}{m} \equiv \binom{\big\lfloor \frac np \big\rfloor}{\big\lfloor \frac mp \big\rfloor} \binom{n \bmod p}{m \bmod p} \pmod{p}

其中 \binom{n}{m} 表示组合数（或者二项式系数），表示从 n 个不同元素中选取 m 个元素的不同方式的数目，其计算公式为

\binom{n}{m} = \frac{n!}{m!(n-m)!}

特别地，当 n < m 时，规定 \binom{n}{m} = 0。

【例题】P2480[SDOI2010] 古代猪文

:::info[题目描述]{open}

特别地，规定 \varphi(1) = 1。

【基本性质】

设 k, m, n \in \mathbb{Z}^+

\bar{a} = \Set{ x \in \mathbb{Z} | x \equiv a \pmod{m} }

称为 a 模 m 的 同余类（或剩余类），其中 a 称为该同余类的 代表元。所有模 m 同余类的集合记为

\mathbb{Z}_m = \{ \bar{0}, \bar{1}, \ldots, \overline{m-1} \}

【基本性质】

设 m \in \mathbb{Z}^+, a, b \in \mathbb{Z}。

  1. 等价关系：同余关系 \equiv \pmod{m} 是整数集 \mathbb{Z} 上的等价关系，同余类就是等价类
  2. 划分性质：不同的同余类互不相交，且全体同余类的并集为 \mathbb{Z}
  3. 代表元的选取：每个同余类有无数个代表元，通常选取 0, 1, \ldots, m-1 作为标准代表元
  4. 运算的良定性：在 \mathbb{Z}_m 上可定义加法和乘法： \bar{a} + \bar{b} = \overline{a+b}, \quad \bar{a} \cdot \bar{b} = \overline{ab}

    这些运算与代表元的选取无关（良定义）

  5. 可逆元：在 \mathbb{Z}_m 中，\bar{a} 可逆当且仅当 \gcd(a, m) = 1，可逆元的个数为 \varphi(m)

    剩余系

    【定义】

    设 m \in \mathbb{Z}^+，若一个大小为 m 的整数集合 \{a_1, a_2, \dots, a_m\} 其元素模 m 两两不同余，则称之为模 m 的一个完全剩余系，通常取 \{0, 1, \dots, m-1\} 作为标准完全剩余系。

若一组整数 b_1, b_2, \dots, b_{\varphi(m)} 满足：

则称 \{b_1, b_2, \dots, b_{\varphi(m)}\} 为模 m 的一个简化剩余系（或既约剩余系）。

【基本性质】

设 m \in \mathbb{Z}^+, a_i, b_i, c, k \in \mathbb{Z}

  1. 平移不变（完全）：若 \{a_1, a_2, \dots, a_m\} 是模 m 的完全剩余系，则对任意整数 c,

    \{a_1 + c, a_2 + c, \dots, a_m + c\}

    也是

  2. 数乘不变（完全）：若 \{a_1, a_2, \dots, a_m\} 是模 m 的完全剩余系且 \gcd(k, m) = 1,
    则 \{ka_1, ka_2, \dots, ka_m\} 也是

  3. 数乘不变（简化）：若 \{b_1, b_2, \dots, b_{\varphi(m)}\} 是模 m 的简化剩余系且

    \gcd(k, m) = 1, \quad \text{则 } \{kb_1, kb_2, \dots, kb_{\varphi(m)}\}

    也是

  4. 威尔逊定理：若 p 为素数，则 1, 2, \dots, p-1 构成模 p 的简化剩余系，且有

    (p-1)! \equiv -1 \pmod{p}

    欧拉定理

    【定义】欧拉定理

    若 a, n \in \mathbb{Z}^+ 且 \gcd(a, n) = 1，则

    a^{\varphi(n)} \equiv 1 \pmod{n}

    【定义】费马小定理

    若 a, p \in \mathbb{Z}^+ 且 p 是素数，则

    a^{p-1} \equiv 1 \pmod{p}

    【推论】费马小定理

    若 a, p \in \mathbb{Z}^+ 且 p 是素数，则

    a^{-1} \equiv a^{p-2} \pmod{p}

因此，可以使用快速幂求模素数下的逆元。

【证明】欧拉定理

设与 n 互素的所有正整数为 r_1, r_2, \dots, r_{\varphi(n)}，它们构成模 n 的一个简化剩余系
由于 \gcd(a, n) = 1，当这些数分别乘以 a 后，得到的数

ar_1, ar_2, \dots, ar_{\varphi(n)}

在模 n 意义下仍然构成一个简化剩余系（即它们模 n 两两不同余，且每个数仍与 n 互素）
因此，这两个集合在模 n 意义下是相同的，于是有

\prod_{i=1}^{\varphi(n)} r_i \equiv \prod_{i=1}^{\varphi(n)} (ar_i) \pmod{n}

即

\prod_{i=1}^{\varphi(n)} r_i \equiv a^{\varphi(n)} \prod_{i=1}^{\varphi(n)} r_i \pmod{n}

每个 r_i 与 n 互素，所以 \prod_{i=1}^{\varphi(n)} r_i 也与 n 互素，故可约去，得

a^{\varphi(n)} \equiv 1 \pmod{n}

【定理】扩展欧拉定理

设 a, m 为正整数，b 为非负整数，则：

  1. 若 \gcd(a, m) = 1，则

    a^b \equiv a^{b \bmod \varphi(m)} \pmod{m}

  2. 若 \gcd(a, m) \neq 1 且 b < \varphi(m)，则直接计算 a^b \pmod{m}

  3. 若 \gcd(a, m) \neq 1 且 b \geq \varphi(m)，则

    a^b \equiv a^{(b \bmod \varphi(m)) + \varphi(m)} \pmod{m}