OI初等数论 Pt1.基础知识

· · 个人记录

引入

如果说数论是数学体系中专门用来研究数字性质的一个分支，那么初等数论则是对整数的性质进行系统性的探讨与研究。千万不要因为其中的“初等”二字小瞧这初等数论尽管名称和学习难度上都没有高等数论那么有逼格，就像初等数学之于高数，数论的所有内容均筑基于此。其中欧几里得证明的算数基本定理（一切合数都可被分解为有限个质数的乘积）在质数筛、GCD（以及LCA)计算、无理数证明等问题上均有用武之地。可以说高等数论奠基于初等数论。它同时也是初学者接触数论的必经之路。

Part1.  前置知识

Div1. 数论有关定理

算术基本定理：每一个合数都可以被分解为有限个质数的乘积。即对于任意合数n，都存在：

**推论一**：正整数$n$的正因数集合为： $\{n=p_{1}^{b_1}p_{2}^{b_2}p_{3}^{b_3}...p_{i}^{b_i} \mid 1 \leq b_i \leq c_i, 1 \leq i \leq k\}

推论二：正整数n的正因数个数为：\tau (n)= (c_1+1) \cdot(c_2+1) \cdot (c_3+1) ... (c_k+1) =\prod_{i=1}^{k}\left( c_i+1\right) \\

推论三：正整数n的所有正因数之和为

\sigma(n)=(p_1+p_1^2+...+p_1^{c_1}+1)\times (p_2+p_2^2+...+p_2^{c_2}+1)\times...\times (p_k+p_k^2+...+p_k^{c_k}+1)=\prod_{i=1}^{k}\frac{p_k^{c_k+1}}{p_k-1}

质数分布定理：区间[1,N]中，当N\to \infty时，质数个数\pi (x)\approx \frac{n}{\ln n}。

费马小定理： 若p是一个质数，则a^p\equiv a\bmod p（\equiv为同余符号）。

欧拉定理（费马小定理扩展）： 若a\perp n（a与n互质），则有a^{\varphi{(n)}} \equiv 1 \bmod n，其中\varphi(n)为欧拉函数。

Div2. 同余

同余，顾名思义，两个数分别除以一个正整数m后得到相同的余数。即a\bmod m=b\bmod m。但是它的定义给出了这样一句话：“对于正整数a和b，若(a-b)\mid m（a-b能被m整除），则称a和b对模m同余，记作a\equiv b\pmod m”。当然以上两种说法是等价的。

同余具有以下三种基本性质：

  1. 反身性：对于任何正整数a，a\equiv a\pmod m
  2. 对称性：即对于a\equiv b\;(\bmod m)，有b\equiv a\pmod m
  3. 传递性：若a\equiv b\pmod m，且b\equiv c\pmod m，有a\equiv c\pmod m

当然，它可以延申到计算机的模运算（毕竟出现了\bmod）。模运算有三种基本运算：

  1. 加运算：(a+b)\% m=(a\% m+b\% m)\% m
  2. 减运算：(a-b)\%m=(a\%m-b\%m)\%m
  3. 乘运算：(a\cdot b)\%m=((a\%m)*(b\%m))\%m

还有两个推论：

  1. 幂运算：a^b\%p=((a\%p)^b)\%p
  2. 求和运算：(\sum\limits_{x=1}^{n}x)\%p=(\sum\limits_{x=1}^{n}x\%p)\%p

同余消去原则：

若同余号两端的项相等，且都与模n互质，则可以同时消去

举例：a\cdot c\equiv b\cdot c \bmod n，如果gcd(c,n)=1，则a\cdot c\equiv b\cdot c\Rightarrow a\equiv b \bmod n。