数论笔记（Full Version）

一、数论基础：

1、整除：

1. 重新定义除法：
   对于计算式：\(a\div b\) 来说，其结果可以变化为以下的式子：$$a = \lfloor \frac{a}{b} \rfloor + a \bmod b$$其中，\(\lfloor \dfrac{a}{b} \rfloor\) 为商，\(a \bmod b\) 为余数。

2. 定义：对于任意计算式 \(a\div b\) 来说，若其余数为 \(0\)，则我们称作 \(b\) 能整除 \(a\)，记做 \(b\mid a\)。

2、质数（素数）：

1. 定义：指除了 \(1\) 和其本身以外不能再被其他数所整除的数，我们称其为质数。
2. 几个经典的质数：\(2,3,10^9+7\)。

3、模运算：

1. 性质：
   1. 加法：\((a+b)\bmod c = (a\bmod c+b\bmod c)\bmod c\)。
   2. 减法：\((a-b)\bmod c=(a\bmod c - b\bmod c + c)\bmod c\)。
   3. 乘法：\((a\times b)\bmod c = a\bmod c \times (b\bmod c) \bmod c\)。

4、\(\gcd(a,b)\) 和 \(\operatorname{lcm}(a,b)\)：

1. \(\gcd(a,b)\)：
   1. 作用：求得 \(a\)，\(b\) 的最大公因数。
   2. 性质：
      1. \(\gcd(a,b) = \gcd(b,a)\)。
      2. \(\gcd(a,b) = \gcd(-a,b)\)。
      3. \(\gcd(a,b) = \gcd(|a|,|b|)\)。
      4. 若有 \(d\mid a\) 且 \(d \mid b\)，则有 \(d\mid \gcd(a,b)\)。
      5. \(\gcd(a,0) = a\)。
      6. \(\gcd(a,ka) = a\)。
      7. \(\gcd(an,bn) = n \gcd(a,b)\)。
      8. \(\gcd(a,b) = \gcd(a,ka+b)\)。
   3. 实现：辗转相除法（欧几里得算法）：

5、同余：

1. 定义：对于两个数 \(a\)、\(b\)，如果 \(a \bmod m = b \bmod m\)，那么我们就称 \(a\) 和 \(b\) 在模 \(m\) 的意义下同余，记做：\(a \equiv b \pmod m\)。

2. 性质：

   1. 若 \(m \mid (a-b)\)，则我们可以称 \(a\) 和 \(b\) 在模 \(m\) 的意义下同余。
   2. 若 \(a = mq + b\)，则我们可以称 \(a\) 和 \(b\) 在模 \(m\) 的意义下同余。
   3. 若 \(a \equiv 0 \pmod m\)，则称 \(m\mid a\)。
   4. 反身性：\(a\equiv a\pmod m\)。
   5. 对称性：若 \(a\equiv b \pmod m\)，那么 \(b\equiv a \pmod m\)。
   6. 传递性：若 \(a\equiv b \pmod m\)，\(b\equiv c \pmod m\)，那么 \(a\equiv c \pmod m\)。
   7. 同余式相加：若 \(a\equiv b \pmod m\)，\(c \equiv d \pmod m\)，那么 \(a\pm c\equiv b\pm d \pmod m\)。
   8. 同余式相乘：若 \(a\equiv b\pmod m\)，\(c \equiv d\pmod m\)，那么 \(ac\equiv bd \pmod m\)。
   9. 同余幂运算：若 \(a\equiv b\pmod m\)，那么 \(a^n\equiv b^n \pmod m\)。

6、同余类和剩余系：

1. 剩余系：
   1. 定义：是指模正整数 \(n\) 的余数所组成的集合。
      1. 完全剩余系：一个包含了正整数 \(n\) 所有可能的余数的剩余系叫做完全剩余系，记做 \(Z_n\)。
      2. 简化剩余系：包含了完全剩余系中所有与 \(n\) 互质的数的剩余系，记做 \(Z^*_n\)。
      3. 在完全剩余系之下，所有的运算全部在模 \(n\) 意义下进行的。
2. 同余类：将满足同余关系的所有整数看作成一个同余等价类。