数论

长文警告。显然的性质略去不写或不证。

本文研究数论，故所有字母默认代表整数。

整除、约数和倍数

定义 若对于 $a,b\in\mathbb{Z},a\ne 0$，$\exists q\in\mathbb{Z},b=aq$，我们称 $b$ 能被 $a$ 整除，记作 $a\mid b$。反之则 $b$ 不被 $a$ 整除，记作 $a\nmid b$。

若 $a\mid b$，则 $a$ 是 $b$ 的约数（因数），$b$ 是 $a$ 的倍数。特殊的，$0$ 是所有非 $0$ 整数的倍数。对于 $b\ne 0$，$\pm 1,\pm b$ 是 $b$ 的平凡约数。其他则称为真约数（非平凡约数）。一般只考虑正整数之间的整除关系。

带余除法

定义 对于任意整数 $a\ne 0,b$，必然存在唯一的 $q,r$ 使得 $b=aq+r\land 0\le r<|a|$，我们称 $a\bmod b=r$ 为余数，$q$ 为商，上述过程为带余除法，$\bmod$ 为取模运算。这里只讨论最小非负余数带余除法。

素数 & 合数

定义 设正整数 $p>1$。如果 $p$ 除了平凡约数外没有其他约数，那么称 $p$ 为素数，反之为合数。这里只讨论正素数。这样，正整数分成了三类：$1$、素数和合数。

性质 1 任意正整数 $n$ 的素因数中至多一个大于 $\sqrt{n}$。

性质 2 若大于 $1$ 的正整数 $n$ 满足 $\forall p\in [1,\sqrt{n}]\cup\mathbb{P},\,p\nmid n$ 那么 $n\in\mathbb{P}$。

证明 2 反证法，若 $n$ 为合数，则 $\exists p,q,\,n=pq,\,2\le p\le q$。故 $p^2\le n$ 即 $p\le\sqrt{n}$。可得 $p$ 的素因子 $\le\sqrt{n}$，且为 $n$ 的约数，矛盾。

性质 2 体现了一个 $O(\sqrt{n})$ 时间判定 $n$ 是否是质数的算法：枚举 $p$ 并试除即可。

最大公约数 & 最小公倍数

定义 一组整数的公约数整除组中所有整数。最大公约数为最大的公约数，记作 $\gcd(a_1,\dots,a_n)$。

同理，一组整数的公倍数被组中所有整数整除。最小公倍数为最小的公倍数，记作 $\operatorname{lcm}(a_1,\dots,a_n)$。

不引起歧义的情况下，可以简记 $(a,b)=\gcd(a,b),[a,b]=\operatorname{lcm}(a,b)$。

特殊的，我们定义若干个 $0$ 的 $\gcd$ 和 $\operatorname{lcm}$ 均为 $0$。

裴蜀（Bézout）定理

裴蜀定理 对于任意整数 $a,b$，存在整数 $x,y$ 使得 $ax+by=\gcd(a,b)$。

证明 一般使用辗转相除法。当 $a=0$ 或 $b=0$ 时，可以发现定理成立。同时 $\gcd(a,b)=\gcd(a,-b)$，故与符合无关。综上不妨设 $a,b>0$ 且 $a\ge b$，$d=\gcd(a,b)$。

将 $a$ 带余除以 $b$，即 $a=bq_1+r_1$ 其中 $0\le r_1\le b$，$q_1,r_1$ 为整数。若 $r_1=0$ 则辗转相除法结束，反之将 $b$ 带余除以 $r_1$，依次按下式进行带余除法：

$\begin{aligned} a&=bq_1+r_1&(0\le r_1<a)\\ b&=r_1q_2+r_2&(0\le r_2<r_1)\\ r_1&=r_2q_3+r_3&(0\le r_3<r_2)\\ &\qquad\vdots&\vdots\qquad\quad\\ r_{n-2}&=r_{n-1}q_n+r_n&(0\le r_n<r_{n-1})\\ r_{n-1}&=r_nq_{n+1}&(0=r_{n+1}<r_n)\\ \end{aligned}$

因为 $r_{n+1}=0$，退出。

从第一个到第 $n$ 个式子依次可以得到 $d\mid r_1,d\mid r_2,\dots,d\mid r_n$，故 $d\le r_n$。

同时从第 $n+1$ 个到第一个依次可得 $r_n\mid r_{n-1},r_n\mid r_{n-2},\dots,r_n\mid b,r_n\mid a$。即 $r_n$ 是 $a,b$ 的公约数。又因为 $d$ 是 $a,b$ 的最大公约数，$d\ge r_n$。

综上所述，$d=r_n$，即 $\gcd(a,b)=r_n$。

由第 $n$ 个式子可得

$d=r_{n-2}-r_{n-1}q_n$

由第 $n-1$ 个式子可得

$r_{n-1}=r_{n-3}-r_{n-2}q_{n-1}$

代入

$\begin{aligned} d&=r_{n-2}-r_{n-1}q_n\\ &=r_{n-2}-(r_{n-3}-r_{n-2}q_{n-1})q_n\\ &=(q_nq_{n-1}+1)r_{n-2}-(q_n)r_{n-3} \end{aligned}$

于是我们用 $r_{n-2},r_{n-3}$ 的线性组合表示了 $d$。以此类推，我们也可以用 $a,b$ 的线性组合表示 $d$。

$\square$

算术基本定理

算术基本引理 设 $p\in\mathbb{P},p\mid a_1a_2 \implies p\mid a_1\lor p\mid a_2$。

算术基本定理（唯一分解定理） 对于任意正整数 $a$，必然有表示

$a=\prod_{i=1}^{n}p_i^{\alpha(i)}$

其中 $p_i$ 均为素数，$\alpha_i$ 均为正整数，且满足 $\forall 1\le i<n,\,p_i<p_{i+1}$。上式也称标准素因数分解式，其对于 $a$ 唯一。同时，我们记 $\nu_{p(i)}(a)=\alpha_i$，即 $a$ 的分解中 $p_i$ 的幂次。

同余

定义 对于整数 $m\ne 0$，若 $m\mid (a-b)$，则 $m$ 称为模数，$a$ 同余于 $b$ 模 $m$。记作 $a\equiv b\pmod m$。另一种等价的定义是：$a,b$ 除以 $m$ 所得的余数相同。

一般的，只讨论 $m$ 为正整数，$b$ 为最小非负整数的情形。

类似等于，同余为等价关系，具有自反性、对称性、传递性，并可以左右同时进行线性运算、乘方。

同余类 & 剩余系

定义 对于所有的 $0\le i<m$，我们称 $\{j|j\bmod m=i\}$ 为模 $m$ 意义下的同余类，即同一个同余类内的数对模 $m$ 同余。

如果 $i$ 还满足 $i\perp m$，则 $\{j|j\bmod m=i\}$ 还称为既约同余类。

定义 在模 $m$ 的剩余类中各取一个元素，则这 $m$ 个数就构成了模 $m$ 的一个 （完全）剩余系。

在模 $m$ 的既约剩余类中各取一个元素，则这 $m$ 个数就构成了模 $m$ 的一个既约剩余系（缩剩余系，简化剩余系）。

数论函数

定义 数论函数即定义域为正整数的函数，也可以视作一个数列。

若该函数 $f(n)$ 还满足对于任意互质正整数 $x,y$，都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为积性函数。

更严格的，若 $f(n)$ 满足对于任意正整数 $x,y$，都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为完全积性函数。

费马（Fermat）小定理

欧拉（Euler）定理

$a^b\equiv \begin{cases} a^{b\bmod\varphi(m)}&\gcd(a,m)=1\\ a^b,&\gcd(a,m)\ne 1,b<\varphi(m)\\ a^{(b\bmod\varphi(m))+\varphi(m)}&\gcd(a,m)\ne 1,b\ge\varphi(m) \end{cases}\pmod m$

中国剩余定理（CRT）

威尔逊（Wilson）定理

参考

• https://oi-wiki.org/math/number-theory/basic/