前言

笔者的课程需要群论，故恶补一下数论基础知识
参考：高教社《初等数论》（第四版）

本文是笔者自己的笔记，所以在描述上面可能偏口语化，请读者见谅

整除与整除的基本性质

整除的定义

首先我们从整除的核心定义开始重新回顾它
::: align-center
对整数 $m,n\in \mathbb{Z}$ ，我们说“m整除n”记作 $m\mid n$ ，是指 $m\ne0$ 且存在整数（0和负数也算） $q$ 使得 $n=qm$

:::
常用的说法还有：

$m$ 是 $n$ 的因子（divisor/factor）
$n$ 被 $m$ 整除（is divisible by）
$n$ 是 $m$ 的倍数（multiple）

如果不存在这样的整数，就记作 $m \nmid n$
要注意的是，0不当因子，即 $m\ne 0$ ，但对于0当n，即当被除数时，每个非零整数都整除0，因为 $q$ 可以取0，此时 $m$ 可以任意，有 $0=0\cdot m$

整除的基本性质

如果 $a\mid b$ 且 $a\mid c$ ，则 $a\mid (b+c)$ （公因子对和仍然是公因子）
如果 $a\mid b$ 且 $b\mid c$ ，则 $a\mid c$ （传递性）
如果 $a\mid b$ ，则对任意整数 $k$ ， $a\mid bk$ （乘以倍数不改变因子关系）

证明：
（1）若 $a\mid b,a\mid c$ 则有 $b=ka, c=qa$ ，则有 $b+c=(k+q)a$ ，由整除定义得 $a\mid (b+c)$
（2）若 $a\mid b$ 则有 $b=qa$ ， $b\mid c$ 又有 $c=kb$ ，故有 $c=qa=qka$ ，由整除定义得 $a\mid c$
（3）易得

另外可以由1和3得到整除得线性封闭推论：若 $a\mid b$ 且 $a\mid c$ ，则对任意整数 $k,l$ ，都有 $a\mid (kb+lc)$ ，此推论非常重要

适当因子、极大因子与素数

定义 $m$ 和 $n$ 是正整数

若 $m\mid n$ 且 $0 ，那么 m 是 n 的适当因子（Proper Divisor），当 n>1 时 m 必然有平凡适当因子1，而当 n=1 时其没有任何的适当银子。需要注意的是当 n>1 时若我们将1去掉，则此时剩下的叫非平凡因子（Nontrivial Divisor）$
若 $m$ 是适当因子，并且对所有 $q\in \mathbb{N}$ ，只要 $m\mid q$ 且 $q\mid n$ ，就必有 $q=m$ 或 $q=n$ ，那么 $m$ 是 $n$ 的极大因子（Maximal Divisor）。
考虑 $n$ 的素因子分解 $n=p_1^{r_1}p_2^{r_2}\cdots p_s^{r_s}$ ，则极大因子正好是 $\frac{n}{p_i}$
若 $n\ge 2$ ，唯一的正因子是 $1$ 和 $n$ ，那么此数就叫素数（Prime）。2是唯一的偶素数，1不是素数

素数定理

素数定理（Prime Number Theorem）是关于素数个数的一个重要数学定理。它表明，当 $x$ 趋近于无穷大时，不超过 $x$ 的素数个数 $\pi(x)$ 与 $\frac{x}{\ln x}$ 的比值趋近于1，这表明随着 $x$ 的增大，从不超过 $x$ 的整数中选一个数是素数的概率大约为 $\frac{1}{\ln x}$

需要注意的是，对于大整数，手算加法的复杂度为 $O(n)$ ，手算乘法的复杂度为 $O(n^2)$ ，而如果要对这个大整数进行素因数分解，首先需要检查所有小于等于 $\sqrt{n}$ 的素数

为什么要检查到 $\sqrt{n}$ ？首先由因数的对称性：对于大于 $1$ 的正整数 $n$ ，若存在整数 $a(1能整除n，则必然存在另一个整数b=\frac{n}{a}满足$

$a\times b=n$
若 $a>\sqrt{n}$ 则 $b=\frac{n}{a}<\sqrt{n}$

假设 n 是合数（非素数），但所有 $\le \sqrt{n}$ 的整数都无法整除 $n$ 。根据因数对称性，所有 $\ge \sqrt{n}$ 的整数也无法整除 $n$ （因为它们的配对因数 $\le \sqrt{n}$ ，而已假设这些配对因数不整除 $n$ ）。这与 $n$ 是合数（存在非 $1$ 和自身的因数）矛盾，因此假设不成立。若 $n$ 是合数，必然存在 $\le\sqrt{n}$ 的因数；若 $\sqrt{n}$ 的整数都无法整除 $n$ 则 $n$ 是素数

假设试除到 $\sqrt{n}$ 时，我们已经把 $n$ 中所有 $\le\sqrt{n}$ 的素因数都除尽了，得到剩余数 $m$ （m = n÷(所有已记录的素因数)）。此时

若 $m=1$ ：说明 $n$ 的所有素因数都 $\le \sqrt{n}$ ，分解完成，没有大于 $\sqrt{n}$ 的素因数
若 $m>1$ ：则 $m$ 必然是素数，且 $m>\sqrt{n}$ ，反证如果 $m$ 是合数，那么由上面的推导 $m$ 必有一个素因数 $p\le\sqrt{m}$ ，但有前提条件 $m\le n\Rightarrow \sqrt{m}\le\sqrt{n}$ ，于是得到 $p\le\sqrt{n}$ ，这与我们的假设“已经把所有小于 $\sqrt{n}$ 的素因数除尽”矛盾，因此 $m$ 只能是素数，故大于 $\sqrt{n}$ 的素因数（如果存在），只会以 “最后剩余的 $m$ ” 的形式出现，我们不需要查找大于 $\sqrt{n}$ 的素数

扯回来，再由素数定理得到小于 $\sqrt{n}$ 的素数个数为 $\pi(\sqrt{n})=\frac{\sqrt{n}}{\ln\sqrt{n}}$ ，复杂度 $O(\sqrt{n})$ ，而在计算机中考虑到数字 $n$ 由二进制存储，它的实际存储位数 $b=floor(\log_2(n))$ ，姑且按 $\log_2n$ 计算，得到 $\sqrt{n}=2^{\frac{1}{2}\log_2 n}=2^{\frac{b}{2}}$ ，实际复杂度为指数级 $O(2^{\frac{b}{2}})$ ，若 $n$ 是一百位整数（b约为332），那么在使用朴素算法的情况下现有的超级计算机进行素因数分解也需要宇宙级时间，因为大整数素因数分解的困难使得它成为RSA等非对称加密算法的基石，另一应用广泛的由ECDSA为代表的椭圆曲线加密，它基于椭圆曲线离散对数问题，这里不再提到

除法算法和GCD

带余除法

设 $a,b\in\mathbb{Z}$ ，则存在唯一的整数 $q,r$ ，使得 $a=bq+r$ ，并且 $0\le r，其中q叫做商（quotient），r叫做余数（remainder）$

注意 $b$ 必须是正数，否则余数 $r$ 不唯一，余数 $r$ 必须落在 $[0,b)$ ，这样才能保持唯一性

证明：
固定 $a,b, b>0$ ，考虑集合 $S=\{a-kb: k\in\mathbb{Z},a-kb\ge 0\}$ ，这是所有形如 $a-kb$ 且非负的数的集合。

首先说明 $S$ 非空，若 $a\ge 0$ ，取 $k=0$ 就有 $a\in S$ ，如果 $a<0$ ，选一个合适的负整数 $k$ 让 $a-kb\ge 0$ 即可。

其次，由于 $S$ 是非空的负整数集合，因此由良序原理（自然数集的每个非空子集都有一个最小元素），它有是最小元的，记为 $r$ ，由 $r\in S$ 得存在整数 $q$ 使得 $r=a-qb$ ，即 $a=bq+r$ 且 $r\ge 0$

再证明 $r，反证若r\ge b那么r-b\ge 0，又r=a-qb于是r'=a-(q+1)b\ge 0，说明r'\in S，且r'，与r是S的最小元矛盾$

最后证唯一性，若 $a=bq+r=bq'+r'$ ，且 $0\le r,r'，做差得到b(q-q')=r'-r，右边的绝对值小于b，但左侧是b的倍数，若要让b的某个倍数得到比b还小的整数这个数只能是0，故r'-r=0，即r'=r$

最大公约数GCD

GCD的定义

设 $a,b$ 是非负整数，且不同时为0， $d$ 称为 $a$ 和 $b$ 的最大公约数（Greatest Common Divisor, GCD），记作 $gcd(a,b)$ ，当且仅当

$d$ 是 $a$ 和 $b$ 的公共因子： $d\mid a$ 且 $d\mid b$
对于任意公共因子 $c$ ，都有 $c\le d$

通常我们只取正的gcd，所以它一般是一个正整数（或者当1的个数为0时等于另一个的绝对值，见下）

GCD的性质

对任意整数 $a,b,c$

$gcd(a,b)=gcd(b,a)$ （对称性）
若 $a\ne 0$ ，则 $gcd(a,0)=|a|$
$gcd(a,b)=gcd(|a|,|b|)$
若 $d=gcd(a,b)$ ，则 $gcd(\frac{a}{d},\frac{b}{d})=1$

粗略地证明：
（1）公因子谁跟谁都是一样的，故当然是对称的
（2） $gcd(a, 0)$ 要保证整除0，而所有非0整数都能整除0，现在要求找一个还能整除 $a$ 自己的因子，最大的正因子就是 $|a|$
（3）由整除的基本性质3，因子关系对负号不敏感， $d\mid a$ 可立即得 $d\mid (-a)$ ，所以公共因子的集合，对 $(a,b)$ 和 $(|a|,|b|)$ 是一样的，因此最大公约数也相同
（4）也就是约掉gcd后变成互素，因为 $d$ 已经吸收了所有的公共因子，再往下就没有别的公共因子了，俩一除剩下的俩数自然是互素的

欧几里得算法（辗转相除法）

给定正整数 $a\ge b>0$ ，反复使用带余除法算法

$a=q_1b+r_1, 0\le r_1$
$b=q_2r_1+r_2, 0\le r_2$
$r_1=q_3r_2+r_3, 0\le r_3$
继续...
$r_{k-2}=q_kr_{k-1}+r_k,0\le r_k$
最后某一步会出现余数为0的情况 $r_{n-2}=q_nr_{n-1}+0$

此时 $gcd(a,b)=r_{n-1}$ ，即最后一个非零余数就是gcd(a,b)

需要注意的是：余数列 $b > r_1 > r_2 >\cdots \ge 0$ 严格递减、且非负，因此必定在有限步内降到0

证明：
（1）证明 $r_{n-1}$ 是 $a$ 和 $b$ 的公因子
反推，从最后一步开始， $r_{n-2}=q_nr_{n-1}$ ，所以 $r_{n-1}\mid r_{n-2}$ ，由因为 $r_{n-1}$ 整除自己，有 $r_{n-1}\mid r_{n-1}$ ，由因为 $r_{n-3}=q_{n-1}r_{n-2}+r_{n-1}$ ，由整除的基本性质1得到 $r_{n-1}\mid r_{n-3}$ ，向前递推得到 $r_{n-1}\mid a$ 且 $r_{n-1}\mid b$
（2）证明任意公共银租 $d$ 都整除 $r_{n-1}$
正推，若 $d\mid a$ 且 $d\mid b$ ，第一步有 $r_1=a-q_1b$ ，由整除的基本性质1得到 $d\mid r_1$ ，向后递推得到 $d\mid r_{n-1}$

故得到 $r_{n-1}$ 是一切公因子的“最大的代表”，也就是我们的 $gcd(a,b)$ 了

若 $a,b$ 各有至多 $n$ 位十进制数字，那么欧几里得算法在至多 $O(n)$ 步内结束

贝祖恒等式与扩展欧几里得算法

Bézout 恒等式（又叫做裴蜀恒等式）阐明：
::: align-center
设 $a,b\in\mathbb{Z}$ 不同时为0，则存在整数 $x,y$ 使得 $gcd(a,b)=xa+yb$

:::
它表明 $gcd(a,b)$ 可以倍写成 $a$ 和 $b$ 的一个整数线性组合，其证明是通过将欧几里得算法得到等式有后向前回代得到的，而我们“回代”的这个过程+欧几里得算法=扩展欧几里得算法，所谓“扩展”，是指在求gcd的同时扩展出对应的线性组合系数 $x,y$

互素与欧几里得引理

互素

定义：整数 $a,b$ 互素（Coprime/Relatively Prime），当且仅当 $gcd(a,b)=1$

注意：互素不代表 $a,b$ 这俩本身是素数，而只是说这俩没有大于1的公共因子

互素的特征（贝祖形式）

由贝祖恒等式可以立即得到： $a,b$ 互素当且仅当存在整数 $x,y$ 满足 $ax+by=1$

证明：
（1）充分性：如果 $gcd(a,b)=1$ ，又贝祖恒等式可以得证
（2）必要性：如果有整数 $x,y$ 满足 $ax+by=1$ ， $a,b$ 的任何公共因子既要整除 $a$ 又要整除 $b$ ，由整除的基本性质1得到也要整除 $ax+by$ ，由等式得到要整除1，而能整除1的只有 $\pm 1$ ，gcd通常取最大正数，即得 $gcd(a,b)=1$ ， $a,b$ 互素

贝祖形式经常被用来证明互素，在考虑用贝祖形式证明互素时只要能构造出 $ax+by=1$ 就行

GCD的性质4的证明

再次回顾前面GCD的性质4：若 $a,b$ 非零， $d=gcd(a,b)$ ，则 $gcd(\frac{a}{d},\frac{b}{d})=1$ ，即 $\frac{a}{d},\frac{b}{d}$ 这俩是互素的

证：
首先使用贝祖恒等式，有 $d=gcd(a,b)$ ，两边同除 $d$ （ $d\ne 0$ ）后满足贝祖形式，充分必要条件得 $\frac{a}{d},\frac{b}{d}$ 这俩肯定是互素的

互素时的整除性质

当 $a,b$ 非零且互素（ $gcd(a,b)=1$ ）时，若 $a\mid c$ 且 $b\mid c$ ，则 $ab\mid c$

证明：
由 $a\mid c,b\mid c$ 和整除定义得到 $c=ra=sb$ ，其中 $r,s\in\mathbb{Z}$ ，其次由 $a,b$ 互素，写为贝祖形式得到 $xa+yb=1$ ，两侧同时乘 $c$ 后，用 $c=ra=sb$ 带入整理后得到 $ab(sx+ry)=c$ ，故 $ab\mid c$

欧几里得引理

设 $p$ 是素数， $a,b\in\mathbb{Z}$ ，如果 $p\mid ab$ ，则 $p\mid a$ 或 $p\mid b$ （或者二者均成立）

证：
假设 $p\nmid a$ ，只要得到 $p\mid b$ 证明即完成
因为 $p$ 是素数，又 $p\nmid a$ ，则 $p$ 和 $a$ 的唯一公共因子就是1，故 $gcd(p,a)=1$ ，由贝祖恒等式得到 $xp+yb=1$ ，两边同时乘 $b$ 得到 $pbx+aby=b$ ，显然p整除自己，有 $p\mid p$ ，由整除的基本性质3得到 $p\mid pbx$ ，又由题目条件 $p\mid ab$ 得到 $p\mid aby$ ，由整除的基本性质1得到 $p\mid (pbx+aby)$ 即 $p\mid b$ ，得证

欧几里得引理告诉我们：素数很贪婪，若其整除某个整数，则要么其“吃掉”其中的一个因子，要么“吃掉”另一个因子

两个重要推论

推论1：若 $p$ 是素数且 $p\mid a_1a_2\cdots a_n$ ，则 $p\mid a_k$ 对某个 $k$ 成立

证：由欧几里得引理立得

推论2：若 $p$ 和 $q_1,\cdots,q_n$ 都是素数，而且 $p\mid q_1\cdots q_n$ ，则 $p=q_k$ 对某个 $k$

证：由推论1知 $p\mid q_k$ 对某个 $k$ ，而素数之间能整除只有一种情况就是俩相等

广义欧几里得引理（互素版本）

进一步扩展欧几里得引理，得到广义版本：
若 $gcd(m, n)=1$ 且 $m\mid nt$ 则 $m\mid t$

证：
因为 $gcd(m,n)=1$ ，由贝祖恒等式得到 $mx+ny=1$ ，两侧同乘 $t$ 得到 $m(tx)+n(ty)=t$ ，显然 $m\mid m(tx)$ ，又由已知条件 $m\mid nt$ 和整除的基本性质得到 $m\mid m(tx)+n(ty)$ 即 $m\mid t$

二元一次不定方程（线性丢番图方程）

定义

一个二元一次线性丢番图方程是形如
::: align-center
$ax+by=c$

:::
的方程，其中 $a,b,c\in\mathbb{Z}$ 已知，我们要寻找整数解 $x,y\in\mathbb{Z}$

可解性判据

设 $a,b,c$ 为非零整数， $d=gcd(a,b)$ ，方程有整数解当且仅当 $d\mid c$

证：
（1）充分性：如果 $(x_0,y_0)$ 是整数解，即 $ax_0+by_0=c$ ，因为 $d\mid a$ 且 $d\mid b$ ，由整除的基本性质得到 $d\mid (ax_0+by_0)$ ，即 $d\mid c$
（2）必要性：如果 $d\mid c$ ，则 $c=kd$ ，由题目条件 $d=gcd(a,b)$ 和贝祖恒等式得到 $d=x'a+y'b$ ，两边同时乘 $k$ 得到 $c=dk=kx'a+ky'b$ ，故得到 $(x_0,y_0)=(kx',ky')$ 是一个整数解

解的结构

已知 $d=gcd(a,b)$ ，且 $d\mid c$ ，并且 $(x_0,y_0)$ 是一个已知得特解，则该方程的通解为
::: align-center
$(x,y)=(x_0+k\frac{b}{d},y_0-k\frac{a}{d}),k\in\mathbb{Z}$

:::

验证
$\begin{aligned}a(x_0 + k\frac{b}{d}) + b(y_0 - k\frac{a}{d})&= ax_0 + ak\frac{b}{d} + by_0 - bk\frac{a}{d} \\&= ax_0 + by_0 + k\frac{ab}{d} - k\frac{ab}{d} \\&= ax_0 + by_0\\&= c\end{aligned}$

证：
设特解为 $(x_0,y_0)$ ，则 $ax+by=ax_0+by_0=c$ ，做差得到 $a(x-x_0)=b(y_0-y)$ ，两边同除 $d=gcd(a,b)$ 得到 $\frac{a}{d}(x-x_0)=\frac{b}{d}(y_0-y)$ ，可得 $\frac{a}{d}\mid \frac{b}{d}(y_0-y)$ 由GCD的性质4得到 $gcd(\frac{a}{d},\frac{b}{d})=1$ ，接着由广义欧几里得引理得到 $\frac{a}{d}\mid (y_0-y)$ ，所以存在 $k$ 使得 $y_0-y=k\frac{a}{d}$ ，即 $y=y_0-k\frac{a}{d}$ ，回代 $a(x-x_0)=b(y_0-y)$ 得到 $x=x_0+k\frac{b}{d}$

一般求解步骤

求解二元一次不定方程，通常遵循

通过欧几里得算法求得 $d= gcd(a,b)$
通过判据 $d\mid c$ 判断是否存在整数解
若解存在，通过扩展欧几里得算法获得一个 $ax+by=c$ 的一个特解 $(x_0,y_0)$
构造通解 $(x,y)=(x_0+k\frac{b}{d},y_0-k\frac{a}{d})$
再按照约束求得 $k$ ，获得实际情况下的特解

算数基本定理

定理

每个整数 $n>1$ 都可以写成若干个素数的乘积 $n=p_1p_2\cdots p_k$ 且此分解在“因子顺序”下是唯一的，即

存在性：任意 $n>1$ ，一定能分解为素数的乘积（可能只有1个因子，因为 $n$ 自个可能是素数）
唯一性：如果 $n$ 有两种素因子分解，除了排列顺序，所有素数底和指数都一样

证明：
（1）存在性：
对于2，显然成立，假设对于所有 $2\le m都可以写成素数乘积，只要证明n也可以写成素数乘积即可 a. 若n本来就是素数，那么它已经是素数的乘积，无需证明 b. 若n不是素数，则n存在适当因子（Proper Divisor）d,1。取p_1为n的最小适当因子，现证明p_1必为素数$

若 $p_1=ab$ 且 $1，则a\mid p_1，又因p_1是n的适当因子，有p_1\mid n，由整除的传递性得到a\mid n且1，这与p_1是最小适当因子矛盾，故p_1不可分解，没有其他因子，则p_1为素数$

则现在 $n$ 可以写为 $p_1n_1$ ，其中 $n_1=\frac{n}{p_1}，递归向后最后n一定可写为素数的乘积$

证毕
（2）唯一性：
假设有两种素因子分解 $n=p_1p_2\cdots p_r=q_1q_2\cdots q_s$ ，其中 $p_i,q_j$ 都是素数

由等式知 $p_1\mid q_1q_2\cdots q_s$ ，由欧几里得引理得推论2得 $p_1=q_j$ 对某个 $j$ 成立，重排右侧因子，让重排后的 $q_1$ 等于这个 $q_j$ ，于是等式变为
::: align-center
$p_1p_2\cdots p_r=p_1q_2\cdots q_s$

:::
两侧消去 $p_1$ ，此后对右侧再进行上述过程，逐个配对所有因子，最终得到 $r=s$ ，并且在适当重排后有 $p_i=q_i$ 对所有 $i$

推论

推论1：设 $n=p_1^{r_1}p_2^{r_2}\cdots p_s^{r_s}$ ，其中 $p_1,\cdots,p_s$ 是互不相同得素数， $r_i\ge 1$ ，则

所有正因子的结构：任一正因子 $d$ 都形如 $d=p_1^{e_1}\cdots p_s^{e_s}, 0\le e_i\le r_i$
因子的个数：因为每个指数 $e_i$ 都可以在 $0\cdots,r_i$ 中任选，总共 $r_i+1$ 种选法，所以正因子总数是 $(r_1+1)(r_2+1)\cdots (r_s+1)$
极大因子正好为 $\frac{n}{p_i},i=1\cdots s$ ，也就是将 $n$ 的每一个素因子“降一价”

推论2：两个正整数 $a,b$ 互素当且仅当它们的素因子分解中没有共同的素数

如果 $a,b$ 互素，即 $d=gcd(a,b)=1$ ，那么就不可能有素数同时整除 $a$ 和 $b$ （最大公因子已经是最小的1了），即没有共同的素数
反过来，如果没有共同素数，对 $a$ 和 $b$ 的任何公因子 $d$ ，假如里面有不是素数的因子，则由算数基本定理可以被分解为素因子，而这些公共素因子只能来自两边共有的素数，但是已经提到没有共同的素数了，则 $a$ 和 $b$ 互素