数论知识整理
灵乌路空
2019-05-15 10:12:26
# $$ \large \text { 数论知识目录 及 前置知识:} $$
$gyh$ 实在是太 ⑨ 了,没脑子的他只能整理在这里:
如果以下内容中存在错误 ， 请及时通知博主 ， 博主会非常感谢您的指正 ， 并欢迎您把蠢货博主的头 **拧下来**
天真的 $gyh$ 以为写一篇 [基础数论知识整理](https://www.luogu.org/blog/koishikoishi/ji-chu-shuo-lun-zhi-shi-zheng-li) ，一篇 [进阶数论知识整理](https://www.luogu.org/blog/koishikoishi/jin-jie-shuo-lun-zhi-shi-zheng-li) 就可以囊括所有的数论知识了 ， 但是他错了
于是就有了这篇文章，来更条理地整理数论知识。
于 $2019.5.15$ 创建
于 $2019.5.16$ 更新了 **约数：欧拉函数,约数和**
于 $2019.5.19$ 更新了 **欧几里得 与 扩展欧几里得：求解同余方程组**
$$ \text{从此开始，一个天文单位} $$
$$ \downarrow $$
------------
## 前置知识：
- 取整函数 ：
下取整: $\lfloor x\rfloor = $不大于 $x$ 的最大整数 。 例: $\lfloor 5.5\rfloor = 5$ , $\lfloor -1.5\rfloor = -2$.
上取整: $\lceil x \rceil = $ 不小于 $x$ 的最小整数 。 例: $\lceil 5.5 \rceil = 6$ ， $\lceil -1.5\rceil = -1$.
- 整除：
**定义 : 如果 $a$ 是 $p$ 的倍数 ，则 $a$ 被 $p$ 整除 ，记作 $ p\mid a$**
**性质 :**
1. 若 $b\mid a$ , $c\mid a$ , $b\perp c$ 则 $bc\mid a$
2. 若 $a \mid b$ , $b\mid a$ , 则: $\mid a\mid = \mid b\mid$
3. 若 $a\mid b$ , $c \in Z$ ， 则: $a\mid bc$
4. 若 $a\mid b$ , $m\in Z$ , 且 $m \not= 0$ , 则 : $ma \mid mb$
5. 若 $a\mid b$ , $a\mid c$ ,则对于任意 $x,y\in Z$ ,均有 $a\mid xb+yc$
-------------------
## 1. 质数
### [https://www.luogu.org/blog/koishikoishi/zhi-shuo](https://www.luogu.org/blog/koishikoishi/zhi-shuo)
包括以下内容：
- 质因数分解
- 素数判定
- 筛法求素数
- 费马小定理
- 二次探测定理
---
## 2. 约数：
### [https://www.luogu.org/blog/koishikoishi/yue-shuo](https://www.luogu.org/blog/koishikoishi/yue-shuo)
包括以下内容：
- 约数与倍数
- 约数的几种求法
- 对于任意数 $n$ , 求其约数的个数 及 其约数和
- 最大公约数 与 最小公倍数
- 互质
- 欧拉函数
---
## 3.浅谈欧几里得 与 扩展欧几里得
### [https://www.luogu.org/blog/koishikoishi/qian-tan-ou-ji-li-dei-yu-kuo-zhan-ou-ji-li-dei](https://www.luogu.org/blog/koishikoishi/qian-tan-ou-ji-li-dei-yu-kuo-zhan-ou-ji-li-dei)
包括以下内容：
- 欧几里得定理
- 裴蜀定理
- 欧几里得扩展
- 解不定方程
- 解同余方程
- 解模的逆元
- 求解同余方程组
---
## 4.乘法逆元
### [https://www.luogu.org/blog/koishikoishi/solution-p3811](https://www.luogu.org/blog/koishikoishi/solution-p3811)
包括以下内容:
- 扩展欧几里得
- 费马小定理
- 线性递推
- 阶乘递推
---
## 5.杂题选讲
### [https://www.cnblogs.com/luckyblock/p/11630763.html](https://www.cnblogs.com/luckyblock/p/11630763.html)
------------
本文为 @灵乌路空 @Luckyblock 原创
转载请联系作者,并注明出处
~~(虽然这么个小破文肯定不会有人转载的)~~