数论学习笔记

这两天一直再看数论方面的东西，心里也想了很多的东西，凑着现在有时间，写写也整理一下思路。

这几天学习数论的感觉就是内容多、乱杂，性质、定理、公式也太别多。但是思路理清楚，就好了。

在这里推荐和我一样数论刚入门的人，看陈景润写的《初等数论》一书，写的真不错，看完后，让思路清晰不少。书中内容也特别多，我是在汉王电纸书上花了几天才读完的，很多东西非常有意思。第一章一次就给讲了几十条的性质、引理、定理，要都记住真的很难，但是有几个非常有意思。Matrix67 大神写的一篇 blog 也非常的有趣，浅显易懂，在程序员杂志上也发表了， 《跨越千年的RSA算法》。

研究数，首先要从素数研究。为什么说素数是研究数的一个绝佳的突破口呢？ 根据算术基本定理，任何数都可以分解成若干个质因数的乘积的形式，而且形式是唯一的。

素数第一个问题就是素数个数的问题，素数究竟是有穷多个还是无穷多个呢？

欧几里德 用反证法 非常漂亮的进行了证明 > 假设素数有限个，设最大的素数为，P，所以素数为：2、3 、5、 7 ... P > 现在有这样一个数 S = 2357...*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、由欧几里德算法，衍生出来一个重要的贝祖等式：两数的最大公约数可以用两数的整数倍相加来表示