数论入门¶

因数¶

整除¶

若 \(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\) 不能同时 \(<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\) 的全部质因子继续容斥即可得到公式。

\(n\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)	\(11\)	\(12\)	\(13\)	\(14\)	\(15\)
\(\varphi(n)\)	\(1\)	\(1\)	\(2\)	\(2\)	\(4\)	\(2\)	\(6\)	\(4\)	\(6\)	\(4\)	\(10\)	\(4\)	\(12\)	\(6\)	\(8\)

欧拉函数的性质： 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)\)

证明：

充分性

对于 \(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$ 不为完全平方数。

必要性

当 \(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\) 个不同的解。