数论入门

因数

整除

若 $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$，显然

是 $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$ 为奇偶讨论即可。

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

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

即把 $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$，分解为

显然不可能。类似的，对于完全立方，由于 $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$.

反之，设 $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^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$ 的简化剩余系。