#数论入门

#因数

#整除

若 $b$ 能整除 $a$，则记为 $a\mid b$，如 $2\mid 12$. 若 $b$ 不能整除 $a$，则记为 $a\nmid b$，如 $5\nmid 12$.

若 $a\nmid b$，则 $b\div a$ 存在余数 $r$ 且 $0<r<a$，记 $r=a\ \mathrm{mod}\ b$. 例如，$3\ \mathrm{mod}\ 2=1$.

整除具有以下性质：

1. 若 $a\mid b$ 且 $a\mid c$，则 $forall x,y$，有 $a\mid xb+yc$.
2. 若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$.
3. 若 $a\mid b$ 且 $b\mid a$，则 $a=\pm b$.
4. 设 $m\neq 0$，则 $a\mid b$，当且仅当 $ma\mid mb$.

#最大公因数与最小公倍数

设 $a,b$ 是两个不为 $0$ 的整数，能使 $d\mid a$ 和 $d\mid b$ 成立的最大整数 $d$，称为 $a,b$ 的最大公因数，记作 $gcd(a,b$.

设 $a,b$ 是两个不为 $0$ 的整数，能使 $a\mid d$ 和 $b\mid d$ 成立的最小整数 $d$，称为 $a,b$ 的最小公倍数，记作 $mathrm{lcm}(a,b$.

• $forall a,b\in\N,\ \gcd(a,b)\cdot\mathrm{lcm}(a,b)=ab$

证明：设 $displaystyle d=\gcd(a,b),a_0=\frac{a}{d},b_0=\frac{b}{d}$. 根据最大公因数的定义，有 $gcd(a_0,b_0)=1$。$\ \ \ \ \ \ \ \ \text{}$ 再根据最小公倍数的定义，有 $mathrm{lcm}(a,b)=a_0\cdot b_0$. $\ \ \ \ \ \ \ \ \text{}$ 于是 $displaystyle\mathrm{lcm}(a,b)=\mathrm{lcm}(a_0\cdot d,b_0\cdot d)=\mathrm{lcm}(a_0,b_0)\cdot d=a_0\cdot b_0\cdot d=\frac{a\cdot b}{d}$，原命题得证。

• 九章算术 更相减损术： $gcd(a,b)=\gcd(b,a-b)=\gcd(a,a-b),\gcd(2a,2b)=2\gcd(a,b$.

证明：$d\mid a,d\mid b\implies d\mid(a-b$.

• 欧几里得算法：$forall a,b\in\N,b\neq 0,\gcd(a,b)=\gcd(b,a\ \mathrm{mod}\ b$.

证明：分类讨论。

1. 若 $a<b$，则有 $gcd(b,a\ \mathrm{mod}\ b)=\gcd(b,a)=\gcd(a,b$.
2. 若 $a\geq b$，不妨设 $a=q\cdot b+r\ (0\leq r<b$。显然 $r=a\ \mathrm{mod}\ b$. 对于 $a,b$ 的任意公因数 $d$，$$ 因为 $d\mid a,d\mid q\cdot b$，故 $d\mid (a-q\cdot b$，即 $d\mid r$. 因此 $d$ 也是 $b,r$ 的公因数，反之亦成立。$$ 故 $a,b$ 的公因数集合与 $b,a\ \mathrm{mod}\ b$ 的公因数集合相同。于是它们的最大公因数也相等。

#裴蜀定理

设 $a,b\in\Z,ab\neq 0$，则 $exist x,y\in\Z$ 使 $ax+by=\gcd(a,b)=a(x+bu)+b(y-au$

由上易推出两个整数 $a,b$ 互素的充分必要条件是 $exist x,y\in\Z$ 使得 $ax+by=1$。

比如要证明 $21n+4$ 与 $14n+3$ 互素，知道 $3(14n+3)-2(21n+4)=1$ 即可。

例 1：证明 $n!+1$ 与 $n+1)!+1$ 互素。

有 $n+1)(n!+1)-[(n+1)!+1]=n$，于是 $d=\gcd(n!+1,(n+1)!+1)]|n$，又因为 $d|n!$，结合 $d|(n!+1$ 得到 $d=1$，原命题得证。

例 2：记费马数 $F_k=2^{2^k}+1,k\geq 0$，证明若 $m\neq n$ 则 $gcd(F_m,F_n)=1$.

设 $m>n$，只要利用 $F_n|(F_m-2$ 证明 $exist x\in\Z$ 使得 $F_m+xF_n=2$【基本技巧例 2】

设 $d=\gcd(F_m,F_n)]|2$. $F_n$ 显然为奇数故 $d=1$. 因此费马数两两互素。

例 3：设 $a>1,m,n>0$，证明 $boxed{\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1}$

令 $D=\gcd(a^m-1,a^n-1$，只要证明 $a^{\gcd(m,n)}-1]|D$ 及 $D|[a^{\gcd(m,n)}-1$ 即可。

显然 $a^{\gcd(m,n)}-1]|(a^m-1$ 和 $a^{\gcd(m,n)}-1]|(a^n-1$，可以证明 $a^{\gcd(m,n)}-1]|D$.

设 $d=\gcd(m,n$，可选 $u,v>0$，使 $mu-nv=d$. 因此 $D|(a^m-1),D|(a^{mu}-1$，扩展开来 $D|(a^{mu}-a^{nv})=a^{nv}(a^d-1$，故 $D|(a^d-1$. 综合上述原命题得证。

例 4：设 $m,n>0,mn|(m^2+n^2$，证明 $m=n$.

设 $gcd(m,n)=d,m=m_1d,n=n_1d,\gcd(m_1,n_1)=1$①. 已知化为 $m_1n_1|(m_1^2+n_1^2$，从而 $m_1|n_1^2,n_1|m_1^2$. 结合①可得 $m_1=n_1=1,m=n$.

例 5：设 $k$ 为正奇数，证明 $displaystyle\sum_{i=1}^ni$ 整除 $displaystyle\sum_{i=1}^ni^k$.

等价于证明 $n|2\displaystyle\sum_{i=1}^ni^k$ 和 $n+1)|2\displaystyle\sum_{i=1}^ni^k$，显然

$$ \begin{aligned}2\sum_{i=1}^ni^k&=[1^k+(n-1)^k]+[2^k+(n-2)^k]+\dots+[(n-1)^k+1^k]+2n^k&=[1^k+n^k]+[2^k+(n-1)^k]+\dots+[n^k+1^k]\end{aligned} $$

是 $n$ 和 $n+1$ 的倍数。

由上可知，为了证明 $b|a$，只需将 $b$ 分解成若干个两两互素的整数 $b_1,b_2,\dots,b_n$ 之积，证明 $b_i|a$ 即可。

#质数

• 定义：一个正整数无法被除了 $1$ 和它自身之外的任何自然数整除，则成为质数，否则为合数。

• 数量：对于一个足够大的整数 $N$，不超过 $N$ 的质数有 $displaystyle\pi(x)\approx\frac{N}{\ln N}$ 个，所以第 $n$ 个质数约为 $n\ln n$.

• 判定：试除法，若 $N$ 为合数，则存在一个能整除 $N$ 的数 $T$ 且 $2 \leq T \leq \sqrt{N}$.

• 算数基本定理：$N = p_1^{c_1}p_2^{c_2}\dots p_n^{c_n}$，$N$ 的正约数个数 $=\red{\boxed{\displaystyle\prod_{i=1}^{n}(c_i+1)}}$，$N$ 的所有正约数的和 $=\displaystyle\prod_{i=1}^{n}(\displaystyle\sum_{j=0}^{c_i}(p_i)^j)=\red{\boxed{\prod_{i=1}^n\frac{p_i^{c_i+1}-1}{p_i-1}}}$.

一个正整数 $N$ 的约数个数上界为 $2\sqrt{N}$，$1$ ~ $N$ 每个数的约数个数的总和大约为 $N\log N$.

• 设 $b|ac$，若 $gcd(b,c)=1$，则 $b|a$.

• 设 $a,b\in\N^*$ 且 $a,b$ 之积是一个整数的 $k(k\geq 2$ 次幂，若 $gcd(a,b)=1$，则 $a,b$ 都是整数的 $k$ 次幂。一般地，设正整数 $a,b,\dots,c$ 之积是一个整数的 $k$ 次幂，且 $a,b,\dots,c$ 两两互质，则 $a,b,\dots,c$ 都是整数的 $k$ 次幂。

• 对任意正整数 $m$ 及质数 $p$，记 $p^c\Vert m$ 表示 $p^c|m$ 但 $p^{c+1}\nmid m$，即 $p^c$ 是 $m$ 的标准分解中出现的 $p$ 的幂。

• 设 $n>1,p$ 为质数，$p^{c_p}\Vert n!$，则 $c_p=\displaystyle\sum_{l=1}^{+\infty}\lfloor\frac{n}{p^l}\rfloor$

例 1：证明无穷数列 $10001,100010001,\dots$ 中无质数。

记 $displaystyle a_n=1+10^4+\dots+10^{4(n-1)}=\frac{10^{4n}-1}{10^4-1}$，接下来分 $n$ 为奇偶讨论即可。

$$ a_{2k}=\frac{10^{8k}-1}{10^4-1}=\frac{10^{8k}-1}{10^8-1}\cdot\frac{10^8-1}{10^4-1} $$

$$ a_{2k+1}=\frac{10^{4(2k+1)}-1}{10^4-1}=\frac{10^{2(2k+1)}-1}{10^2-1}\cdot\frac{10^{2(2k+1)}+1}{10^2+1} $$

例 2：证明 $forall n\in\N^*,n>1,n^4+4^n$ 不是质数。

$n$ 为偶数显然。$n$ 为奇数时，设 $n=2k+1$，

$$ \begin{aligned}n^4+4^n&=n^4+4\cdot 4^{2k}=n^4+4\cdot (2k)^4=n^4+4n^2\cdot(2^k)^2+4\cdot(2k)^4-4n^2\cdot(2^k)^2&=(n^2+2\cdot 2^{2k})^2-(2n\cdot 2^k)^2=(n^2+2^{k+1}n+2^{2k+1})(n^2-2^{k+1}n+2^{2k+1})\end{aligned} $$

即把 $4^n$ 看成 $4y^4$，有 $red{\boxed{x^4+4y^4=(x^2+2y^2+2xy)(x^2+2y^2-2xy)}}$

练 1：设 $a,b,c,d\in\N^*,ab=cd$，证明 $a+b+c+d$ 不是质数。

例 3：证明：若 $a,b\in\Z,2a^2+a=3b^2+b$，则 $a-b$ 和 $2a+2b+1$ 都为完全平方数。

已知化为 $a-b)(2a+2b+1)=b^2$，设 $d=\gcd(a-b,2a+2b+1$，若 $d>1$，则 $d$ 有质因子 $p$，$p|b^2\implies p|b$，$p|(a-b)\implies p|a\implies p|1$，这不可能，因此 $d=1$. 因为 $b^2$ 是完全平方数，由此可得 $|a-b|，|2a+2b+1|$ 也是完全平方。

只要证 $a-b$ 和 $2a+2b+1$ 不能同时 $<0$ 即可。设 $a-b<0$，则 $b-a=r^2$. 显然 $r|b,r|a$，令 $b=b_1r,a=a_1r$，代入题目 $a_1^2+6a_1r+3r^2+1=0$，得 $a_1=-3r\pm\sqrt{6r^2-1}$，显然 $6r^2-1$ 应为完全平方数，而 $6r^2-1\equiv 2\ (\mathrm{mod}\ 3$，矛盾，原命题得证。

#不定方程

例 1：证明两个连续正整数之积不能是完全平方或完全立方。

反证法，即设 $x(x+1)=y^2$ 有解，则 $2x+1)^2=4y^2+1$，分解为

$$ (2x+1+2y)(2x+1-2y)=1\implies\begin{cases}2x+1+2y=1\2x+1-2y=1\end{cases}\implies x=y=0 $$

显然不可能。类似的，对于完全立方，由于 $x$ 和 $x+1$ 互质，可得它们都是立方数。设 $x=u^3,x+1=v^3,y=uv,v^3-u^3=1=(v-u)(v^2+uv+u^2$，显然不可能。

类似的，可证明连续两个正整数之积不能是整数的 $k(k\geq 2$ 次幂。

练 1：设 $k\in\N^*,k\geq 2$，证明：连续三个正整数之积不能是整数的 $k$ 次幂。

提示：$x(x^2-1)=y^k\implies a^kb^k=(ab)^k,1=a^{2k}-b^k=(a^2)^k-b^k$，导出矛盾。

例 2：证明方程 $y^2+y=x+x^2+x^3$ 没有 $x\neq 0$ 的整数解。

转化为 $y-x)(y+x+1)=x^3$，可以证明 $gcd(y-x,y+x+1)=1$，设 $y-x=a^3,y+x+1=b^3,x=ab$，可得 $b^3-a^3=(b-a)(b^2+ab+a^2)=2ab+1③$，证明该方程无解即可。$ab>0$ 时，$b-a\geq 1$，③的左边 $geq 3ab>$ 右边；$ab<0$ 时，③的左边的绝对值 $geq 2(a^2+b^2-|ab|)>2|ab|>$ ③的右边的绝对值。因此原命题成立。

练 2：求方程 $x^2-y^2)^2=1+16y$ 的所有整数解。

提示：$y\geq 0，|x|\geq$ 或 $leq y+1$，均可得出 $x^2-y^2)^2\geq(2y-1)^2$，得 $2y-1)^2\leq 1+16y$，答案 $x,y)=(\pm 1,0),(\pm 4,3)(\pm4,5$.

例 3：设 $x,y,z\in\N^*,2x^x=y^y+z^z$，证明 $x=y=z$.

$$ (x+1)^{x+1}>x^{x+1}+(x+1)x^x>2x^x\implies y,z\leq x $$

反之，设 $y\geq x+1$，则 $y^y+z^z>(x+1)^{x+1}>2x^x$，矛盾。而 $y^y+z^z\leq x^x+x^x=2x^x$，所以 $x=y=z$.

#欧拉函数

$1$ ~ $N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $varphi(N$. 用数学符号表示即为 $varphi(N)=\displaystyle\sum_{i=1}^{N}[\gcd(i,N)=1$.

若 $N = p_1^{c_1}p_2^{c_2}\dots p_n^{c_n}$，则 $displaystyle\varphi(N)=N\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times\dots\times\frac{p_n-1}{p_n}=N\cdot\displaystyle\prod_{质数p|N}\left(1-\frac{1}{p}\right$

证明：设 $p,q$ 为 $N$ 的不同质因子，$1$ ~ $N$ 中 $p$ 的倍数有 $displaystyle \frac{N}{p}$ 个，$q$ 的倍数有 $displaystyle \frac{N}{q}$ 个。若把 $displaystyle \frac{N}{p}+\frac{N}{q}$ 个数去掉，则 $displaystyle\frac{N}{pq}$ 被计算了 $2$ 次（容斥原理）。因此， $1$ ~ $N$ 中不与 $N$ 含有相同质因子的 $p$ 或 $q$ 数量为 $displaystyle N-\frac{N}{p}-\frac{N}{q}+\frac{N}{pq}=N\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right$，对 $N$ 的全部质因子继续容斥即可得到公式。

欧拉函数的性质：

1. $forall n>1$，$1$ ~ $n$ 中与 $n$ 互质的数的和为 $displaystyle\frac{n\times\varphi(n)}{2}$.
2. 若 $a,b$ 互质，则 $varphi(ab)=\varphi(a)\varphi(b$.
3. 设 $p$ 为质数，$varphi(p)=p-1$.
4. 设 $p$ 为质数，$k\in\N^*,\varphi(p^k)=p^{k-1}\times(p-1)=p^k-p^{k-1}$.
5. 设 $p$ 为质数，若 $p\mid n$ 且 $p^2\mid n$，则 $displaystyle\varphi(n)=\varphi\left(\frac{n}{p}\right)\times p$.
6. 设 $p$ 为质数，若 $p\mid n$ 但 $p^2\nmid n$，则 $displaystyle\varphi(n)=\varphi\left(\frac{n}{p}\right)\times (p-1$.
7. 若 $n$ 为奇数，则 $varphi(2n)=\varphi(n$.
8. $forall n\geq 3,\ n\in\N^*,\ 2\mid\varphi(n$.
9. 欧拉反演：$displaystyle\sum_{d\mid n}\varphi(d)=n$.

证明：

1. 因为 $gcd(n,x)=\gcd(n,n-x$，所以与 $n$ 不互质的数 $x,n-x$ 成对出现，平均值为 $displaystyle\frac{n}{2}$. $$ 因此与 $n$ 互质的数的平均值也是 $displaystyle\frac{n}{2}$，进而得到性质 1。
2. 根据欧拉函数的计算式可直接获得性质 2。
3. 根据欧拉函数的定义可直接获得性质 3。
4. 从 $1$ ~ $p^{k}$ 中的所有数，除了 $p^{k-1}$ 个 $p$ 的倍数外都与 $p^k$ 互素。
5. 若 $p\mid n$ 且 $p^2\mid n$，则 $displaystyle n,\frac{n}{p}$ 包含相同的质因子，只是 $p$ 的指数不同。$$ 按照欧拉函数的计算公式，$displaystyle \frac{\varphi(n)}{\varphi(\frac{n}{p})}=\frac{n}{\frac{n}{p}}=p$，得到性质 5。
6. 若 $p\mid n$ 且 $p^2\mid n$，则 $displaystyle n,\frac{n}{p}$ 互质。因为 $displaystyle\varphi(n)=\varphi\left(\frac{n}{p}\right)\varphi(p$，而 $varphi(p)=p-1$，得到性质 6。
7. $forall m<2n,m\in\N^*$，若 $2\mid m$，则 $gcd(m,2n)\neq 1$，也就是对欧拉函数的值没有贡献；$$ 若 $2\nmid m$，则 $gcd(m,2n)=1$，欧拉函数的值也就与 $2n$ 中的偶质因子无关。
8. $n\geq 3$ 时，与 $n$ 互质的数不可能为 $displaystyle\frac{n}{2}\implies\forall x<n,\gcd(x,n)=\gcd(n-x,n$，也就是存在一一对应关系。
9. 设 $f(n)=\displaystyle\sum_{d\mid n}\varphi(d$，利用 $varphi$ 是积性函数，得到：$$ 若 $n,m$ 互质，则 $f(nm)=\displaystyle\sum_{d\mid nm}\varphi(d)=\displaystyle\sum_{d\mid n}\varphi(d)\cdot\displaystyle\sum_{d\mid m}\varphi(d)=f(n)f(m$，即 $f(n$ 是积性函数。$$ 对于单个质因子有：$begin{aligned}f(p^m)&=\displaystyle\sum_{d\mid p^m}\varphi(d)=\displaystyle\sum_{i=0}^{m}\varphi(p^i)=\varphi(1)+\varphi(p)+\varphi(p^2)+\varphi(p^3)+\dots+\varphi(p^m)&= 1+(p-1)+(p-1)p+(p-1)p^2+\dots+(p-1)p^{m-1}&=1+(p-1)+(p^2-p)+(p^3-p^2)+\dots+(p^m-p^{m-1})=p^m\end{aligned}$ 所以 $f(n)=\displaystyle\prod_{i=1}^{m}f(p_i^{c_i})=\displaystyle\prod_{i=1}^{m}p_i^{c_i}=n$

#积性函数与完全积性函数

若函数 $f(x$ 满足 $f(1)=1$ 且 $forall x,y\in\N^{*},\gcd(x,y)=1$ 都有 $f(xy)=f(x)f(y$，则 $f(x$ 是积性函数。

若函数 $f(x$ 满足 $f(1)=1$ 且 $forall x,y\in\N^{*}$ 都有 $f(xy)=f(x)f(y$，则 $f(x$ 是完全积性函数。

性质：

1. 若 $f(x$ 和 $g(x$ 均为积性函数，则以下函数也为积性函数： $$begin{aligned}h(x)&=f(x^p) \ h(x)&=f^p(x) \ h(x)&=f(x)g(x) \ h(x)&=\displaystyle\sum_{d\mid x}f(d)g\left(\frac{x}{d}\right)\end{aligned}$$
2. 设 $x=\displaystyle\prod p_i^{c_i}$，

若 $f(x$ 为积性函数，则 $f(x)=\displaystyle\prod f(p_i^{c_i}$。

若 $f(x$ 为完全积性函数，则 $f(x)=\displaystyle\prod f^{c_i}(p_i$。

例子：

积性函数：$varphi(n),\sigma k(n)=\displaystyle\sum{d\mid n}d^k,\sigma _0(n$ 通常简记为 $d(n$ 或 $tau(n$，$sigma _1(n$ 通常简记为 $sigma(n$。

完全积性函数：$varepsilon(n)=[n=1],\text{id}_k(n)=n^k,\text{id}_1(n$ 通常简记为 $text{id}(n),f(n)=1$.

#同余

• 平方数 $mathrm{mod}\ 4\equiv 0$ 或 $1,\mathrm{mod}\ 8\equiv0$ 或 $1$ 或 $4,\mathrm{mod}\ 3\equiv 0$ 或 $1,\mathrm{mod}\ 5\equiv0$ 或 $pm 1$.
• 立方数 $mathrm{mod}\ 9\equiv 0$ 或 $pm 1$.
• 四次幂 $mathrm{mod}\ 16\equiv 0$ 或 $1$.

例如可证明 $a,b,c,d\in\N^*,a^{4b+d}-a^{4c+d}$ 能被 $240=2^4\times 3\times 5$ 整除。

例 1：设 $a,b,c\in\Z,a+b+c=0,d=a^{1999}+b^{1999}+c^{1999}$，证明 $d$ 可被 $6$ 整除。

$$ u^{1999}\equiv u(\mathrm{mod}\ 2)\implies d\equiv a+b+c\equiv 0(\mathrm{mod}\ 2)\implies2|d $$

$$ u^3\equiv u(\mathrm{mod}\ 3)\implies u^{1999}\equiv u\cdot u^{1998}\equiv u\cdot u^{666}\equiv u\cdot u^{222}\equiv u^{75}\equiv u^{25}\equiv u^9\equiv u(\mathrm{mod}\ 3) $$

注意 $u^3\equiv u(\mathrm{mod}\ 3$ 是费马小定理的特殊情形。

练 1：设 $x,y,z\in\Z,(x-y)(y-z)(z-x)=x+y+z$，证明 $27|(x+y+z$.

只要证明 $x,y,z$ 两两模 $3$ 同余即可。

练 2：证明 $11,111,1111,\dots$ 不是完全平方数。只要知道 $11\ \mathrm{mod}\ 4\neq 0$ 即可。

例 2：数列 $set{x_n}$ 为 $1,3,5,11,\dots$，满足 $x_{n+1}=x_n+2x_{n-1}$.

数列 $set{y_n}$ 为 $7,17,55,161,\dots$，满足 $y_{n+1}=2y_n+3y_{n-1}$. 证明：两个数列无相同项。

考虑以 $8$ 为模，因为 $x_2\equiv 3,x_3\equiv 5$. 若 $x_{n-1}\equiv 3,x_n\equiv 5$，则 $x_{n+1}\equiv 3,x_{n+2}\equiv 5$.

显然 $set{x_n}$ 是模 $8$ 后的周期数列，同理 $set{y_n}$ 也是（ $7,1,7,1,\dots$ ），于是命题得证。

#费马小定理与欧拉定理

若整数 $a$ 和整数 $b$ 除以正整数 $m$ 的余数相等，则称 $a,b$ 模 $m$ 同余，记为 $a\equiv b\ (\mathrm{mod}\ m$.

并且注意到 $displaystyle k\ \mathrm{mod}\ i=k-\left\lfloor\frac{k}{i}\right\rfloor\cdot i$，且同余满足同加性、同乘性、同幂性，但不满足同除性。

对于 $forall a \in [0, m - 1$，集合 $set{a+km\ (k\in\Z)}$ 的所有数模 $m$ 同余，余数都是 $a$. 该集合称为一个模 $m$ 的同余类，简记为 $overline{a}$.

模 $m$ 的同余类一共有 $m$ 个，分别为 $overline{0},\overline{1},\overline{2},\dots,\overline{m-1}$. 它们构成 $m$ 的完全剩余系。

$1$ ~ $m$ 中与 $m$ 互质的数代表的同余类共有 $varphi(m$ 个，它们构成 $m$ 的简化剩余系。$$ 例如，模 $10$ 的简化剩余系为 $set{\overline{1},\overline{3},\overline{7},\overline{9}}$。

若从某个非空数集中任选两个元素（同一元素可重复选出），选出的这两个元素通过某种（或几种）运算后的得数仍是该数集中的元素，那么，就说该集合对于这种（或几种）运算是封闭的。$$ 例如若一个集合中的元素，如果能够做到做加法运算的结果还在这个集合中，就说这个集合对加法运算封闭。$$ 例如 $N$ 对加法、乘法运算是封闭的；$Z$ 对加、减、乘法运算是封闭的；$mathbb{Q}, \mathbb{C}$ 对四则运算是封闭的。

简化剩余系关于模 $m$ 乘法封闭。这是因为若 $a,b\ (1\leq a,b\leq m$ 与 $m$ 互质，则 $ab$ 也与 $m$ 互质。$$ 由余数的定义得 $ab\ \mathrm{mod}\ m$ 也与 $m$ 互质，即 $ab\ \mathrm{mod}\ m$ 也属于 $m$ 的简化剩余系。

• 费马小定理：若 $p$ 是质数，则对于任意整数 $a$，有 $a^p\equiv a\ (\mathrm{mod}\ p$.
• 欧拉定理：若正整数 $a,n$ 互质，则 $a^{\varphi(n)}\equiv 1\ (\mathrm{mod}\ n$.

证明：设 $n$ 的简化剩余系为 $set{\overline{a_1},\overline{a_2},\dots,\overline{a_{\varphi(n)}}}$. $forall a_i,a_j$，若 $a\cdot a_i\equiv a\cdot a_j\ (\mathrm{mod}\ n$，则 $a\cdot(a_i-a_j)\equiv 0.$ 因为 $a,n$ 互质，所以 $a_i\equiv a_j$. 故当 $a_i\neq a_j$ 时，$aa_i,aa_j$ 也代表不同的同余类。

又因为简化剩余系关于模 $m$ 乘法封闭，故 $overline{aa_1}$ 也在简化剩余系集合中。因此，集合 $set{\overline{a_1},\overline{a_2},\dots,\overline{a_{\varphi(n)}}}$ 与集合 $set{\overline{aa_1},\overline{aa_2},\dots,\overline{aa_{\varphi(n)}}}$ 都能表示 $n$ 的简化剩余系。综上所述：

$$ a^{\varphi(n)}a_1a_2\dots a_{\varphi(n)}\equiv(aa_1)(aa_2)\dots(aa_{\varphi(n)})\equiv a_1a_2\dots a_{\varphi(n)}\ (\mathrm{mod}\ n) $$

因此 $a^{\varphi(n)}\equiv 1\ (\mathrm{mod}\ n$。当 $p$ 为质数时，满足 $varphi(p)=p-1$，两边同乘 $a$ 即可得到费马小定理。

另外，当 $a$ 是 $p$ 的倍数，费马小定理显然成立。

• 欧拉定理的推论：若正整数 $a,n$ 互质，则对于任意正整数 $b$，有 $a^b\equiv a^{b\ \mathrm{mod}\ \varphi(n)}\ (\mathrm{mod}\ n$

证明：设 $b=q\cdot \varphi(n)+r$，其中 $0\leq r<\varphi(n$，即 $r=b\ \mathrm{mod}\ \varphi(n$. 于是有：

$$ a^b\equiv a^{q\cdot\varphi(n)+r}\equiv (a^{\varphi(n)})^q\cdot a^r\equiv 1^q\cdot a^r\equiv a^r\equiv a^{b\ \mathrm{mod}\ \varphi(n)}\ (\mathrm{mod}\ n) $$

证毕。面对 $a+b,a-b,a\cdot b$ 这样的算式，可以在计算前先把 $a,b$ 对 $p$ 取模。面对 $a^b$ 这样的乘方算式，可以先把底数对 $p$ 取模、指数对 $varphi(p$ 取模，再计算乘方。

即 $a^b\equiv (a\ \mathrm{mod}\ p)^{b\ \mathrm{mod}\ \varphi(p)}\ (\mathrm{mod}\ p$

• 扩展欧拉定理

$$a^b\equiv\begin{cases}a^{b\ \mathrm{mod}\ \varphi(m)}&\text{if }\gcd(a,m)=1\ a^b&\text{if }\gcd(a,m)\neq 1,b<\varphi(m)\ a^{b\ \mathrm{mod}\ \varphi(m)+\varphi(m)}&\text{if }\gcd(a,m)\neq 1,b\geq\varphi(m)\end{cases}\ (\mathrm{mod}\ m$$

证明十分显然，略。

• 若正整数 $a,n$ 互质，则满足 $a^x\equiv 1\ (\mathrm{mod}\ n$ 的最小正整数 $x_0$ 是 $varphi(n$ 的约数。

反证法，假设满足 $a^x\equiv 1\ (\mathrm{mod}\ n$ 的最小正整数 $x_0$ 不能整除 $varphi(n$.

设 $varphi(n)=qx_0+r\ (0<r<x_0$，因为 $a^{x_0}\equiv 1\ (\mathrm{mod}\ n$，所以 $a^{qx_0}\equiv 1\ (\mathrm{mod}\ n$. 根据欧拉定理 $a^{\varphi(n)}\equiv 1\ (\mathrm{mod}\ n$，所以 $a^r\equiv 1\ (\mathrm{mod}\ n$. 这与 $x_0$ 最小矛盾。故假设不成立，原命题成立。

#中国剩余定理

设 $m_1,m_2,\dots,m_n$ 是两两互质的整数，$m=\displaystyle\prod_{i=1}^n m_i,M_i=\frac{m}{m_i},t_i$ 是线性同余方程 $M_it_i\equiv 1\ (\mathrm{mod}\ m_i$ 的一个解。对于任意的 $n$ 个整数，方程组

$$ \begin{cases}x\equiv a_1\ (\mathrm{mod}\ m_1) \ x\equiv a_2\ (\mathrm{mod}\ m_2)\ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\ x\equiv a_n\ (\mathrm{mod}\ m_n)\end{cases} $$

有整数解，解为 $x=\displaystyle\sum_{i=1}^{n}a_iM_it_i$，通解可以表示为 $x+km(k\in\Z$，最小非负整数解为 $x\ \mathrm{mod}\ m$.

证明：因为 $displaystyle M_i=\frac{m}{m_i}$ 是除了 $m_i$ 之外所有模数的倍数，所以 $forall k\neq i,a_iM_it_i\equiv 0\ (\mathrm{mod}\ m_i$，$\ \ \ \ \ \ \ \ \ \ \text{}$ 所以代入 $x=\displaystyle\sum_{i=1}^{n}a_iM_it_i$，原方程组成立。

#威尔逊定理

• $p$ 为素数 $xLeftrightarrow{}(p-1)!\equiv -1\ (\mathrm{mod}\ p$

证明：

1. 充分性

对于 $p$ 不是素数的情况，有 $begin{cases} p=1 & (1-1)!\equiv 0\ (\mathrm{mod}\ 1) \ p=4 & (4-1)!\equiv 2\ (\mathrm{mod}\ 4) \ p>4 & 分类讨论得出\ (p-1)!\equiv 0\ (\mathrm{mod}\ p) \end{cases}$

(a) 当 $p$ 为完全平方数。

则 $p=k^2$ 且 $k>2$，用相减法比较 $2k$ 与 $p$ 的大小得 $2k<p$，于是有

$$\begin{aligned}(p-1)!&=1\times 2\times\dots\times k\times\dots\times 2k\times\dots\times (p-1)\\ &=2nk^2\\&=2np\end{aligned}$$

所以 $(p-1)!\equiv 0\ (\mathrm{mod}\ p)$ 且 $p$ 为完全平方数。

(b) 当 $p$ 不为完全平方数。

则 $p$ 可以表示为两个不相等的数 $a$ 和 $b$ 的乘积，设 $a<b$，则有 $p=ab,1<a<b<p$

$$\begin{aligned}(p-1)!&=1\times 2\times\dots\times a\times\dots\times b\times\dots\times (p-1)\\&=a\times b\times n\\ &=np\end{aligned}$$

所以 $(p-1)!\equiv 0\ (\mathrm{mod}\ p)$ 且 $p$ 不为完全平方数。

1. 必要性

当 $p$ 为素数时，考虑二次剩余式 $x^2\equiv 1\ (\mathrm{mod}\ p$，化简得 $x-1)(x+1)\equiv 0\ (\mathrm{mod}\ p$

于是 $x\equiv 1\ (\mathrm{mod}\ p$ 或 $x\equiv p-1\ (\mathrm{mod}\ p$。现在先抛开 $1$ 和 $p-1$ 不管，

$forall a\in [2,p-2$，必然存在一个和它不相等的逆元 $a^{-1}\in[2,p-2$，满足 $aa^{-1}\equiv 1\ (\mathrm{mod}\ p$

所以必然有 $displaystyle\frac{p-3}{2}$ 对数相乘的乘积为 $1$，即 $p-2)!\equiv 1\ (\mathrm{mod}\ p$

等式两边同时乘 $p-1$ 就得到威尔逊定理。

例题：$n\in\N^*$ 且 $n\leq 10^6$，求 $S_n$.

$$ S_n=\displaystyle\sum_{k=1}^{n}\left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor $$

令 $d=3k+7$，原式化简为

$$ S_n=\displaystyle\sum_{k=1}^{n}\left\lfloor\frac{(d-1)!+1}{d}-\left\lfloor\frac{(d-1)!}{d}\right\rfloor\right\rfloor $$

由威尔逊定理，当 $d$ 为素数时，$displaystyle\frac{(d-1)!+1}{d}$ 必然是整数，而 $displaystyle\left\lfloor\frac{(d-1)!}{d}\right\rfloor$ 必然比 $displaystyle\frac{(d-1)!+1}{d}$ 小 $1$，于是有：

$$ \begin{cases}p\ 为素数 & \displaystyle\left\lfloor\frac{(d-1)!+1}{d}-\left\lfloor\frac{(d-1)!}{d}\right\rfloor\right\rfloor=1 \ p\ 为合数 & \displaystyle\left\lfloor\frac{(d-1)!+1}{d}-\left\lfloor\frac{(d-1)!}{d}\right\rfloor\right\rfloor=0\end{cases} $$

所以只需统计 $1,3\times 10^6+7$ 中的素数即可得出答案。

#拉格朗日定理

若 $p$ 是质数，则对于模 $p$ 意义下的 $n$ 次整系数多项式 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_0(p\nmid a_n$ 同余方程 $f(x)\equiv 0(\mathrm{mod}\ p$ 至多有 $n$ 个不同的解。