数论基础的补充讲解整除的一些性质：
(1)
(4)
(7)
(9)
(10)
小数的GCD:
eps
拓展欧几里得:
Ps:关于欧几里得和拓展欧几里得可以参考我的另外一篇博文《欧几里得& 拓展欧几里得算法讲解（Euclid&Extend-EuclidAlgorithm）》
所谓不定方程，即未知数的个数多于方程个数，且未知数受到某些限制（如要求是有理数、整数或正整数等等）的方程或方程组。
如3x-4y==6，方程只有一个，但是解却可以有多个。
求解不定方程的一组解，或者判断不定方程是否有解，扩展欧几里得就可以派上用场了。
（2）求解模线性方程（线性同余方程）：
求解，未知数x的最小解。
（3）求解模的逆元： 同余方程这时称求出的x为a的对模n乘法的逆元。PS：关于逆元，有一个蛮有用的性质：
设p为素数，（a/b）%p=a*b^(p-2)%p，这样就可以将除法处理为乘法。
素数： 定义
素数是大于
非素数称为合数。
素数的eratosthenes筛法
筛法是数论中一个比较重要的算法，在
所谓筛法，就是每次筛去一部分数。如图，起始所有的数都标记为素数，遇到
区间素数
获得
首先线性筛出之间所有的素数
算是模板吧，此处不贴代码~
素数判定 试除法
就是大家都会的简单算法，用小于该数的所有素数去试除，若都无法整除，则为素数，复杂度O(sqrt(N)).
Miller-Robin随机素性测试
关于Miller-Robin算法，可以另劈一章进行讲解，因而此处只做简略介绍。
，一般
因而失误概率很低，适用于大数素性判断。
关于。
唯一分解理论
定义：自然数N皆可以表示为素数之积
一些结论：
①、N的约数个数，为(x1+1)*(x2+1)*……*(xm+1)
分解质因子普通的分解质因数
对
先找一个最小的质数k；
若该质数等于n，则分解质因子的过程已经结束；
若
若
Pollard_rho因数分解
适用于大数的分解质因子，，返回的质因子无序。
欧拉函数中国剩余定理
参考资料：
①、东北师范大学数论基础讲解
版权声明：本文为博主原创文章，未经博主允许不得转载。
我们首先去了象鼻山，那里景色秀丽神奇，
