数论之基础

本文对于数论的开头部分做一个简介。

符号

整除/同余理论常见符号

1. 整除符号：\(x|y\)，表示\(x\) 整除\(y\)，即\(x\) 是\(y\) 的因数。
2. 取模符号：\(x \bmod y\)，表示\(x\) 除以\(y\)得到的余数。
3. 互质符号：\(x \perp y\)，表示\(x,y\) 互质。
4. 最大公约数：\(gcd(x, y)\)，在无混淆意义的时侯可以写作\((x, y)\)。
5. 最小公倍数：\(lcm(x, y)\)，在无混淆意义的时侯可以写作\([x, y]\)。

数论函数常见符号

​ 求和符号：\(\sum\)符号，表示满足特定条件的数的和。举几个例子：
• \(\sum_{i=1}^{n}{i}\)表示\(1+2+...+n\)的和。其中\(i\)是一个变量，在求和符号的意义下\(i\)通常是正整数或者非负整数（除非特殊说明）。这个式子的含义可以理解为，\(i\)从\(1\)循环到\(n\)，所有\(i\)的和。这个式子用代码的形式很容易表达。当然，学过简单的组合数学的同学都知道\(\sum_{i=1}^{n}{i}=\frac{n(n+1)}{2}\)。
• \(\sum_{S \subseteq T}{|S|}\)表示所有被\(T\)包含的集合的大小的和。
• \(\sum_{p \leq n, p\perp n}{1}\) 表示的是\(n\)以内有多少个与\(n\)互质的数，即\(\varphi(n)\)，\(\varphi\) 是欧拉函数。

​ 求积符号：\(\prod\)符号，表示满足特定条件的数的积。举几个例子：
• \(\prod_{i=1}^{n}{i}\)表示\(n\)的阶乘，即\(n!\)。在组合数学常见符号中会讲到。
• \(\prod_{i=1}^{n}{a_i}\)表示\(a_{1}\times a_{2}\times a_{3}\times ...\times a_{n}\)。
• \(\prod_{x|d}{x}\)表示\(d\)的所有因数的乘积。
​ 在行间公式中，求和符号与求积符号的上下条件会放到符号的上面和下面，这一点要注意。

其他常见符号

1. 阶乘符号\(!\)，\(n!\)表示\(1\times 2\times 3\times...\times n\)。特别地，\(0! = 1\)。
2. 向下取整符号：\(\lfloor x \rfloor\)，表示小于等于\(x\)的最大的整数。常用于分数，比如分数的向下取整\(\lfloor \frac{x}{y} \rfloor\)。
3. 向上取整符号：\(\lceil x \rceil\)，与向下取整符号相对，表示大于等于\(x\)的最小的整数。

整除

​ 整除的定义： 设