素数定理：记
定理：设
定理：设
定理：设
（1）
（2）
（3）
定理：设
定理：给定两个互素的正整数
定理：
定理：
定理：任何
关于上述定理的两个结论
（1）如果
证明：如果
很明显能被
Euler函数及其证明：
1.p^k的欧拉函数
对于给定的一个素数p，我们知道φ(p) = p-1。(φ(n)是Euler函数，表示和n互素的小于n的正整数的个数。)
假设一个整数n是p的k次幂，也就是n = p^k，k∈N+
容易证明 φ(n) = p^k - p^(k-1)
证明：已知小于p^k的正整数个数为p^k-1个，其中
和p^k不互质的正整数有{p×1,p×2,...,p×(p^(k-1)-1)}共计p^(k-1)-1个
所以φ(n) = p^k -1 - (p^(k-1)-1) = p^k - p^(k-1)
2.pq的欧拉函数
假设p,q是两个互质的正整数，则pq的欧拉函数为
φ(pq) = φ(p)φ(q)，gcd(p,q)=1（gcd(p,q)表示p与q的最大公约数，gcd(p,q)=1即表示p与q互质）
证明：
∵m= pq, gcd(p,q) =1
∴根据中国余数定理，有Zm和Zp×Zq之间存在一一映射
所以M的完全余数集中元素的个数等于集合Zp×Zq元素的个数
而后者的元素个数为φ(p)φ(q)，所以有 φ(pq) = φ(p)φ(q)
3.任意正整数的欧拉函数
φ(n)=n∏(1-1/p)，其中p为能够被n整除的质数
Euler定理及其证明:
对于互质的整数a和n，有a^φ(n) ≡ 1 (mod n) （1 (mod n)表示除以n后余1的整数）
证明：首先证明下面这个命题：
对于集合Zn={x_1,x_2,...,x_φ(n)}，考虑集合
S = {ax_1(mod n),ax_2(mod n),...,ax_φ(n)(mod n)}
则S = Zn
1) 由于a,n互质，x_i也与n互质，则ax_i也一定于n互质，因此
任意x_i，ax_i(mod n) 必然是Zn的一个元素
2) 对于Zn中两个元素x_i和x_ j，如果x_i ≠ x_ j
则ax_i(mod n) ≠ ax_ j(mod n)，这个由a、n互质和消去律可以得出。
所以，很明显，S=Zn
既然这样，那么
（ax_1 × ax_2×...×ax_φ(n)）(mod n)
= （ax_1(mod n) × ax_2(mod n)× ... × ax_φ(n)(mod n)）(mod n)
= （x_1 × x_2 × ... × x_φ(n)）(mod n)
考虑上面等式左边和右边
左边等于(a^φ(n) ×（x_1 × x_2 × ... × x_φ(n)）mod n)(mod n)
右边等于x_1 × x_2 × ... × x_φ(n)）(mod n)
而（x_1 × x_2 × ... × x_φ(n)）(mod n)和n互质
根据消去律，可以从等式两边约去，就得到：
a^φ(n) ≡ 1 (mod n)（≡表示恒等于）
（2）如果
证明：由结论（1）很容易得到
小贴士： 对于任意的n>=1,b>1 有如下结论
