数论基础笔记

内容基本来自 OI-Wiki。

设 $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\Leftrightarrow -a\mid b\Leftrightarrow a\mid -b\Leftrightarrow |a|\mid |b|$
• $a\mid b\wedge b\mid c\Rightarrow a\mid c$
• $a\mid b\wedge a\mid c\Leftrightarrow \forall x,y\in\mathbb{Z},a\mid (xb+yc)$
• $a\mid b\wedge b\mid a\Leftrightarrow b=\pm a$
• 设 $m=0$，那么 $a\mid b\Leftrightarrow ma\mid mb$
• 设 $b\ne 0$，那么 $a\mid b\Rightarrow |a|\le |b|$
• 设 $a\ne 0,b=qa+c$，那么 $a\mid b\Leftrightarrow a|c$

若 $a\mid b$，则称 $b$ 是 $a$ 的倍数，$a$ 是 $b$ 的约数。

$0$ 是所有非 $0$ 整数的倍数。对于整数 $b\ne 0$，$b$ 的约数只有有限个。

平凡约数：对于整数 $b\ne 0$，$\pm 1,\pm b$ 是 $b$ 的平凡约数。当 $b=\pm 1$ 时，$b$ 只有两个平凡约数。

对于整数 $b\ne 0$，$b$ 的其他约数称为真约数。

约数的性质：

• 设整数 $b\ne 0$，当 $d$ 遍历 $b$ 的全体约数时，$\dfrac{b}{d}$ 也遍历 $b$ 的全体约数。
• 设整数 $b\gt 0$，当 $d$ 遍历 $b$ 的全体正约数时，$\dfrac{b}{d}$ 也遍历 $b$ 的全体正约数。

具体问题中，一般约数指正约数。

设 $a,b\in \mathbb{Z},a\ne 0.$ 设 $d$ 为给定整数，那么，一定存在唯一整数对 $(q,r)$，满足 $b=qa+r,d\le r\lt |a|+d.$

无论 $d$ 取何值，$r$ 统称为余数，$a\mid b$ 等价于 $a\mid r$。

一般情况，$d$ 取零，此时 $b=qa+r,0\le r\lt |a|$ 称为带余除法。这里的余数 $r$ 称为最小非负余数。

余数还有几种常见取法：

1. 绝对最小余数，$d=-\dfrac{|a|}{2}$。
2. 最小正余数，$d=1$。
3. 一般只见于编程语言，不定义 $d$，而是令 $q=\left[\dfrac{b}{a}\right]$，这里 $[x]$ 表示 $x$ 向零取整。

如果没有特殊说明，余数总指最小非负余数。

• 任一整数被正整数 $a$ 除后，余数一定是且仅是 $0$ 到 $(a-1)$ 这 $a$ 个数中的一个；
• 相邻 $a$ 个整数被正整数 $a$ 除后，恰好取到上述 $a$ 个余数，特别地，一定有且仅有一个数被 $a$ 整除。

一组整数的公约数，是指同时是这组数中每一个数的约数的数。$\pm 1$ 是任意一组整数的公约数。

一组整数的最大公约数，是指所有公约数里面最大的一个。

对不全为 $0$ 的整数 $a,b$，将其最大公约数记为 $\gcd(a,b)$，不引起歧义时可简写为 $(a,b)$。

对不全为 $0$ 的整数 $a_1,\dots,a_n$，将其最大公约数记为 $\gcd(a_1,\dots,a_n)$，不引起歧义时可简写为 $(a_1,\dots,a_n)$。

一般认为 $0$ 与 $0$ 的最大公约数不存在，但考虑函数实现，也可以定义为 $0$。C++ STL 的实现采用后者。

一组整数的公倍数，是指同时是这组数中每一个数的倍数的数。$0$ 是任意一组整数的公倍数。

一组整数的最小公倍数，是指所有正的公倍数里面，最小的一个数。

对整数 $a,b$，将其最小公倍数记为 $\operatorname{lcm}(a,b)$，不引起歧义时可简写为 $[a,b]$。

对整数 $a_1,\dots,a_n$，将其最小公倍数记为 $\operatorname{lcm}(a_1,\dots,a_n)$，不引起歧义时可简写为 $[a_1,\dots,a_n]$。

最大公约数和最小公倍数有如下性质：

• $(a_1,\dots,a_n)=(|a_1|,\dots,|a_n|)$；
• $(a,b)=(b,a)$；
• 若 $a\ne 0$，则 $(a,0)=(a,a)=|a|$；
• $(bq+r,b)=(r,b)$；
• $(a_1,\dots,a_n)=((a_1,a_2),a_3,\dots,a_n)$；进而 $\forall 1\lt k\lt n-1,~(a_1,\dots,a_n)=((a_1,\dots,a_k),(a_{k+1},\dots,a_n))$；
• 对不全为 $0$ 的整数 $a_1,\dots,a_n$ 和非零整数 $m$，$(ma_1,\dots,ma_n)=|m|(a_1,\dots,a_n)$；
• 对不全为 $0$ 的整数 $a_1,\dots,a_n$，若 $(a_1,\dots,a_n)=d$，则 $(a_1/d,\dots,a_n/d)=1$；
• $(a^n,b^n)=(a,b)^n$；
• 若 $b|ac,(a,b)=1$，则 $b\mid c$；
• 若 $b|c,a|c,(a,b)=1$，则 $ab\mid c$；
• 若 $(a,b)=1$，则 $(a,bc)=(a,c)$；
• 若 $(a_i,b_j)=1,~\forall 1\leq i\leq n,1\leq j\leq m$，则 $\left(\prod_{i} a_i,\prod_{j} b_j\right)=1$；特别地，若 $(a,b)=1$，则 $(a^n,b^m)=1$；
• 对整数 $a_1,\dots,a_n$，若 $\exists v\in \mathbb{Z},\prod_i a_i=v^m$，且 $(a_i,a_j)=1,\forall i\ne j$，则 $\forall 1\leq i\leq m,~\sqrt[m]{a_i}\in\mathbb{Z}$；
• $[a_1,\dots,a_n]=[|a_1|,\dots,|a_n|]$；
• $[a,b]=[b,a]$；
• 若 $a\ne 0$，则 $[a,1]=[a,a]=|a|$；
• 若 $a\mid b$，则 $[a,b]=|b|$；
• $[a_1,\dots,a_n]=[[a_1,a_2],a_3,\dots,a_n]$。进而 $\forall 1\lt k\lt n-1,~[a_1,\dots,a_n]=[[a_1,\dots,a_k],[a_{k+1},\dots,a_n]]$；
• 若 $a_i\mid m,~\forall 1\leq i\leq n$，则 $[a_1,\dots,a_n]\mid m$；
• $[ma_1,\dots,ma_n]=|m|[a_1,\dots,a_n]$；
• $[a,b,c][ab,ba,ca]=[a,b][b,c][c,a]$；
• $[a^n,b^n]=[a,b]^n$；
• $(a,b)[a,b]=|ab|$；
• $(ab,bc,ca)[a,b,c]=|abc|$；
• $\dfrac{(a,b,c)^2}{(a,b)(b,c)(a,c)}=\dfrac{[a,b,c]^2}{[a,b][b,c][a,c]}$。

设整数 $p\ne 0,\pm 1$，如果 $p$ 除了平凡约数外没有其他约数，称 $p$ 为质数；

若整数 $a\ne 0,\pm 1$，如果 $a$ 不是质数，称 $a$ 为合数。

$p$ 与 $-p$ 同为质数或同为合数。如果没有特殊说明，质数一般限定在正数。

质数的其他性质可以参考我之前写的 质数及素性判断，这里不再列出。

设 $p$ 为质数，$p\mid a_1a_2$，则 $p\mid a_1$ 和 $p\mid a_2$ 至少有一个成立。

又称唯一分解定理。

设正整数 $a$，必有 $$a=p_1p_2\dots p_s$$

其中 $p_j(1\le j\le s)$ 是质数。在不计次序意义下，该表示唯一。

在上述表示中，将相同的质数合并， $$a=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_s^{\alpha_s}(p_1\lt p_2\lt\dots\lt p_s),$$

叫做正整数 $a$ 的标准质因数分解式。

设整数 $m\ne0$。若 $m\mid(a-b)$，称 m 为 模数（模），$a$ 同余于 $b$ 模 $m$，$b$ 是 $a$ 对模 $m$ 的 剩余。记作 $a\equiv b\pmod m$。

否则，$a$ 不同余于 $b$ 模 m，$b$ 不是 $a$ 对模 $m$ 的剩余。记作 $a\not\equiv b\pmod m$。

这样的等式，称为模 $m$ 的同余式，简称同余式。

同余是等价关系，换句话说，同余满足自反性¹、对称性²、传递性³。

数论函数指定义域是正整数的函数，因此也可以视为一个数列。

积性函数是数论函数的一种，具有特殊的性质。

若数论函数 $f(n)$ 满足 $f(1)=1$ 且 $\forall a,b\in\mathbb{N},(a,b)=1$ 都有 $f(ab)=f(a)f(b)$，称 $f(n)$ 为积性函数；

若数论函数 $f(n)$ 满足 $f(1)=1$ 且 $\forall a,b\in\mathbb{N}$ 都有 $f(ab)=f(a)f(b)$，称 $f(n)$ 为完全积性函数。

若 $f(n)$ 和 $g(n)$ 均为积性函数，则下列函数也是积性函数：

• $h(n)=f(n^p);$
• $h(n)=f^p(n);$
• $h(n)=f(n)g(n);$
• $h(n)=\sum_{d\mid n}f(d)g\left(\dfrac{n}{d}\right).$

其中最后一个形式也记作 $h=f\ast g$，称 $h$ 是 $f$ 和 $g$ 的卷积。