数论基础

尽量不用奇怪的符号

整除

对于任意正整数 $a,b$ ，如果 $a$ 是 $b$ 的因数，则说 $b$ 可被 $a$ 整除，记作 $a|b$。

余数

$a$ 除以 $b$ 的余数是在 $[0,b-1]$ 范围内的整数，记作 $a\mathrm{\%}b$ 或者 $amodb$，读作 $a$ 对 $b$ 取模（或取余）。

性质：一个数字 $x$ 对任何数取模，结果一定小于$\frac{x}{2}$。

证明：

当被模数 $p\le \frac{x}{2}$ 时，余数处在 $[0,p-1]$ 范围内，小于 $\frac{x}{2}$。

当被模数 $p>\frac{x}{2}$ 时，$x\mathrm{\%}p=x-p<\frac{x}{2}$。

同余

如果两个数字 $a,b$ 对 $m$ 取模后的值相等，则称 $a,b$ 对 $m$ 同余。

记作 $a\equiv b(modm)$。

随时取模定理：

在算数过程中取模不影响最终答案。

$$\begin{gathered} (a+b)modp=((amodp)+(bmodp))modp \\ (a-b)modp=((amodp)-(bmodp))modp \\ (a\ast b)modp=((amodp)\ast (bmodp))modp \end{gathered}$$

性质（只列一些不太平凡的）：

$$\begin{gathered} ac\equiv bc(modm)\iff a\equiv b(mod\frac{m}{gcd(c,m)}) \\ a\equiv b(modm)\iff gcd(a,m)=gcd(b,m) \end{gathered}$$

第一个性质解释：

可以将取模看作一个长度为 $m$ 的环，从起点出发走 $ac$ 步和 $bc$ 步最后走到 $acmodm$ 处。

如果只走 $a$ 步和 $b$ 步，并且最终还落在同一位置，那么必须一次走 $c$ 个点，那么环上实际会被走到的点只有 $\frac{m}{gcd(n,m)}$个。

第二个性质：涉及更相减损术。

素数

只有 $1$ 和自己本身作为因子的数是素数。

$1$ 既不是质数也不是合数。

性质：合数 $x$ 至少存在一个质因子小于等于 $\sqrt{x}$。

证明：假设 $p\ast q=x$，若 $p,q>\sqrt{x}$，则 $p\ast q>x$，矛盾。

$1\sim n$ 中素数的个数数量级约等于$\frac{n}{ln(n)}$。（证明过于数学略）。

如果两个数字 $a,b$ 的最大公共因子为 $1$ ，称数字 $a,b$ 互素（互质），记作 $a\perp b$。

算术基本定理

也叫唯一分解定理：

任意正整数 $a$ ，有唯一的：

$$a=p_1^{k_1}\ast p_2^{k_2}\ast \dots \ast p_n^{k_n}=\prod _{i=1}^n{p}_i^{k_i}$$

其中 $p_i$ 是互不相同的质数。

每个数字都可以被素数唯一地分解表示。

积性函数

若函数 $f(x)$ 满足 $f(1)=1$ ，且对于任意互质的两个数字 $a,b$ ，都有 $f(ab)=f(a)\ast f(b)$ ，则称 $f$ 为积性函数。

若函数 $f(x)$ 满足 $f(1)=1$ ，且对于任意两个数字 $a,b$ 都有 $f(ab)=f(a)\ast f(b)$，则称 $f$ 为完全积性函数。

如果 $f$ 和 $g$ 是积性函数，则以下 $h$ 也是积性函数：

$$\begin{gathered} h(x)=f(x^p) \\ h(x)=f^p(x) \\ h(x)=f(x)g(x) \\ h(x)=\sum _{d|x}f(d)g(\frac{x}{d}) \end{gathered}$$

练习题

B2020 分糖果

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

P5436 【XR-2】缘分

P2926 [USACO08DEC] Patting Heads S

P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目