数论学习笔记

这两天一直再看数论方面的东西，心里也想了很多的东西，凑着现在有时间，写写也整理一下思路，学习数论的第一感觉就是东西多，乱杂，性质定理公式太别多。但是思路理清楚，就好了。在这里推荐和我一样数论刚入门的人，看陈景润写的初等数论一书，我感觉写的真不错，看完后，思路感觉非常的清晰。当然东西也特别多，东西真是一次无法看完呀，但是我感觉有很多的东西非常的有意思，比如说的数论的性质引理定理什么的第一章一次就给出来的有几十条的东西，要都记住真的很难，但是有几个非常有意思。还有matrix 67大神写的一篇blog也非常的有意思，浅显易懂，在程序员杂志上也发表了名字叫跨越千年的RSA算法。

    说素数， 首先从素数说起，素数真的是研究数的一个绝佳的突破口，为什么呢？根据算术基本定理一下就能想明白了吧？？？任何数都可以分解成若干个质因数的乘积的形式，而且形式是唯一的如果不考虑因数乘积位置上不同的形式问题的话。

   素数第一个问题就是素数个数的问题，素数究竟是有穷多个还是无穷多个呢？欧几里德给出了一个非长漂亮的证明，假设素数有限个，设最大的素数为，P，所以素数为：2、3 、5、 7 .。。。。。。。P现在有这样一个数 S = 2*3*5*7*。。。。*P +1，既然有了算数基本定理，那么这个问题就可以简化了， 只需要找在所有的质数里面，有没有一个数是S的约数，从S的式子，可以看出S不管除以任何素数 K 都会余 1，说明S没有因数，除了它本身S和1之外，说明S为素数，且S > P,但是刚才我们已经假设P为最大的素数，与假设矛盾，故素数为无限个。素数个数的问题，用反证法非常漂亮的给证明了。说完素数，因该还有一个听上去相近的概念，就是互素，互素的两个数不一定都是素数，两个合数也可能互素比如 9 和16，质数肯定是互素的。那素数的个数是怎么分布的呢？还有一个问题在1到n-1这n-1个数里面有多的数是与n互素的那？？其实第二个问题就是欧拉函数phi（n）。第一个问题其实素数定理已经解决了：

Pi(N)/N *LgN = 1 当N为无穷大的时候，pi（n）为< N的素数的个数。

第二个问题其，人已经给出来了，怎么求？

首先设n = P1^Q1*P2*Q2**。。。。*Pk^Qk.那么phi（n） = n(1-1/P1)(1-1/P2)******(1-1/Pk),，然后把每一项的1 移到分子上去  然后把n乘进去就得到了。
 
phi(n) = (P1^n-P1^(n-1))*(P^2^n-P2^(n-1))*。。。。。(Pk^n-Pk^(n-1))
 
= P1^（n-1）(P1-1)*P2^（n-1）(P2-1)*.......*Pk^（n-1）(Pk-1)。

然后计算机j就能很快的算出来phi（n）了。算phi(n)的时间复杂度大概为Ln(n)级别的。

int  Eu(int n){ int ans = 1; 
    for(int i = 2; i * i <= n;++i){  
        if(!(n%i)){  
            ans *= i - 1;  
            n /= i;  
            while(!(n%i)){  
                ans *= i;n/=i;   
            }   
        }  
    }  
    if(n > 1){  
        ans *= n -1;  
    }  
    return ans;  
}  

但是当算 从 1 到N之间所有数的欧拉函数的时候这个时候就可能会出现TLE了，但是有改进的办法，就是用线性筛选素数的方法，在里面家几句话，就可以成为线性筛选欧拉函数了。呵呵。

int phi[3000010];  
int prime[3000010],prime_top = 0;  
int not_prime[3000010];   
//算 2 到3000000的所有数的欧拉函数。   
void build_phi(){  
    memset(not_prime,0,sizeof(not_prime));  
      
    for(int i = 2;i < 3000010;++i){  
        if(!not_prime[i]){  
            prime[prime_top++] = i;  
            phi[i] = i - 1;  
        }  
        for(int j = 0;j<prime_top&&i*prime[j]<3000010;++j){  
            not_prime[i*prime[j]] = 1;  
            //找到第一个能被 i整除的此次筛选结束进行下一次。   
            if(i%prime[j] == 0){  
                phi[i*prime[j]] = prime[j] * phi[i];  
                break;  
            }else{  
                phi[i*prime[j]] = phi[i] *(prime[j] - 1);  
            }  
        }  
    }  
}  




 2、由欧几里德算法，衍生出来一个重要的贝祖等式：两数的最大公约数可以用两数的整数倍相加来表示