定义：除了1和本身两个数都不能被整除的自然数叫做质数，否则为合数。
0和1既不是质数也不是合数，最小的合数是4，
最小的质数是2，是唯一的偶质数，质数有无穷多个
由质数定理可以给出第n个质数p(n)的渐进估计：p(n)≈nlnn

二、唯一分解定理（算术基本定理）

任意大于1的自然数都能被质数的质数幂的乘积表示
运用：试除法（质因数分解或求一个数的约数）、质数判定
由此衍生出埃式筛法和线性筛法（欧拉筛法）
线性筛法时间复杂度为O(n)

先将2的倍数删去，再将3的倍数删去，即按顺序将质数的倍数删去

让每个合数只被最小的素因子筛除,这样每个数最多只被筛一次。
这个性质被广泛运用于数论函数的求解
洛谷P3383 【模板】线性筛素数

唯一分解定理（算术分解定理）的推论

如果一种转移关系j->i且j是i的约数，那么有两种方法
一个数约数个数上限为2sqrt n
倍数法：O(nlogn)先枚举j再枚举倍数i。
显然倍数法时间复杂度更优
有的情况可以用埃式筛法，当然倍数法会更加广泛

三、最大公约数与最小公倍数

四、求两个数的最大公约数

定义1：给定正整数m，若用m除两个整数a和b所得余数相同，称a和b对模m同余，记作a≡b(mod m)，并称该式子为同余式；否则称a和b对模m不同余
定义2：整数的集合被分为m个不同的集合，这些集合被称为模m剩余类（同余类）。每个同余类的任意两个整数都是模m同余的。

七、欧拉定理和费马小定理

八、裴蜀定理与欧几里得算法

十、中国剩余定理（CRT）

十一、扩展中国剩余定理（ExCRT）

用扩展欧几里得算法合并两个方程组
数学归纳法：假设求出了前k-1个方程构成的方程组的一个解x，记m=lcm(m1,m2,…,mk-1)， 则x+im(i为任意整数)是前k-1个方程的解。
其中t是未知量，可以用扩展欧几里得判断该方程是否有解。如果有解，求出t值，则前k个方程构成的方程组的一个解为x’=x+tm。
特别的，第一个方程的解x=a1

欧拉计划 解决一些数学问题的项目： : 。 以伦纳德·欧拉命名： : 2014 年 3 月 29 日：问题 1。3 或 5 的倍数之和。第 359659 个人解决此问题。 04/01/2014：问题 2。偶数斐波那契数的总和。 解决此问题的第 297816 人。 2014 年 4 月 30 日：问题 3。最大的质因数。 解决此问题的第 222097 人。 2014 年 5 月 24