数论中几个比较基础的知识点

对于任意整数分解质因数得到：N=P1^x1* P2^x2 *……*Pn*xn;

1. 欧拉函数

通式：M(N）=M*(1-1/p1) *(1-1/p2)*……*(1-1/pn)

性质：

a. 若N是质数p的k次幂，则M(N)= p^k-p^(k-1)=(p-1)p^(k-1)=n-n/p;

b.若是奇数,则M(N)=M(2*N);

c.若x,y互质，则M(x*y)=M(x)*M(y)

2. 整数因子和

通式：M=(P1^0+P1^1+…+P1^x1)*(P2^0+P2^1+…+P2^x2)*…*(Pn^0+Pn^1+…+Pn^xn)

（一个大牛指点我的，我自己推导的公式，不知道对不对）

3. 欧拉定理

若 gcd(a,b)=1

则 a^M(b) ≡1 (mod b)

其中 M(b) 是欧拉函数

4.整数因子个数

M=（x1+1） * （x2+1） * …… *（xn+1）

5.欧拉函数线性方程

必定存在唯一解使得

ax+by=gcd(a,b)

数论入门看了好几天了，还是没有找到“门”，伤不起啊，好吧，果断转移路线，缓冲一下，开始学习xiaod最近学习的两个算法，加油！