欧拉函数 ：
欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 n ，小于 n 且和 n 互质的正整数（包括 1）的个数，记作 φ(n) 。
完全余数集合：
定义小于 n 且和 n 互质的数构成的集合为 Zn ，称呼这个集合为 n 的完全余数集合。
显然 |Zn| ＝φ(n) 。
有关性质：
对于素数 p ，φ(p) = p -1 。
对于两个不同素数 p， q ，它们的乘积 n = p * q 满足 φ(n) = (p -1) * (q -1) 。
这是因为 Zn = {1, 2, 3, ..., n{p, 2p, ..., (q{q, 2q, ..., (p1)1)1) = (p -1) * (q -1) ＝φ(p) * φ(q) 。
欧拉定理 ：
对于互质的正整数 a 和 n ，有 a
φ(n)
≡ 1 mod n
。
证明：
( 1 ) 令 Zn = {x1, x2, ..., xφ(n)} ， S = {a * x1 mod n, a * x2 mod n, ..., a * xφ(n) mod n} ，
则 Zn = S 。
① 因为 a 与 n 互质， xi (1 ≤ i ≤ φ(n)) 与 n 互质， 所以 a * xi
与 n 互质，所以 a * xi
mod n ∈ Zn 。
② 若 i ≠ j ， 那么 xi ≠ xj，且由 a, n互质可得 a * xi mod n ≠ a * xj mod n （消去律）。
( 2 )
a* x1 * x2 *...* xφ(n) mod n
≡ (a * x1) * (a * x2) * ...* (a * xφ(n)) mod n
≡ (a * x1 mod n) * (a * x2 mod n) * ...* (a * xφ(n) mod n) mod n
≡
x1 * x2 * ...* xφ(n) mod n
φ(n)
对比等式的左右两端，因为 xi
(1 ≤ i ≤ φ(n)) 与 n 互质，所以 a
≡
1 mod n （消去律）。
注：
消去律：如果 gcd(c,p) = 1 ，则 ac ≡ bc mod p ⇒ a ≡ b mod p 。
费马定理 ：
若正整数 a 与素数 p 互质，则有 appk -1
证明：
小于 pk 的正整数个数为 pk1-1)} 共计 pk1 个
所以 φ(n) = pk(pk1) = pk1 。
( 2 ) p * q 的欧拉函数
假设 p, q是两个互质的正整数，则 p * q 的欧拉函数为 φ(p * q) = φ(p) * φ(q) ， gcd(p, q) = 1 。
证明：
令 n = p * q ， gcd(p,q) = 1
根据中国余数定理，有
Zn 和 Zp × Zq 之间存在一一映射 （我的想法是：
a ∈ Zp ， b ∈ Zq ⇔ b * p + a * q ∈ Zn 。）
所以 n 的完全余数集合的元素个数等于集合 Zp × Zq 的元素个数。
而后者的元素个数为 φ(p) * φ(q) ，所以有
φ(p * q) = φ(p) * φ(q) 。
( 3 ) 任意正整数的欧拉函数
任意一个整数 n 都可以表示为其素因子的乘积为：
I
n = ∏ piki (I 为 n 的素因子的个数)
i=1
根据前面两个结论，很容易得出它的欧拉函数为：
I
I Φ(n) = ∏ piki-1(pi-1) = n∏ (1 - 1 / pi)
i=1
i=1
对于任意 n > 2，2 | Φ(n) ,因为必存在
pi -1 是偶数。
//直接求解欧拉函数
int euler(int n){ //返回euler(n)
int res=n,a=n;
for(int i=2;i*i
if(a%i==0){
res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出
while(a%i==0) a/=i;
}
}
if(a>1) res=res/a*(a-1);
return res; }
//筛选法打欧拉函数表
#define Max 1000001 int euler[Max]; void Init(){
euler[1]=1;
for(int i=2;i
euler[i]=i;
for(int i=2;i
if(euler[i]==i)
for(int j=i;j
euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出
}
证明：
( 1 ) 令 Zn = {x1, x2, ..., xφ(n)} ， S = {a * x1 mod n, a * x2 mod n, ..., a * xφ(n) mod n} ，
则 Zn = S 。
#① 因为 a 与 n 互质， xi (1 ≤ i ≤ φ(n)) 与 n 互质， 所以 a * xi 与 n 互质，所以 a * xi mod n ∈ Zn 。
#② 若 i ≠ j ， 那么 xi ≠ xj，且由 a, n互质可得 a * xi mod n ≠ a * xj mod n （消去律）。
( 2 ) aφ(n) * x1 * x2 *...* xφ(n) mod n
≡ (a * x1) * (a * x2) * ...* (a * xφ(n)) mod n ≡ (a * x1 mod n) * (a * x2 mod n) * ...* (a * xφ(n) mod n) mod n ≡ x1 * x2 * ...* xφ(n) mod n 对比等式的左右两端，因为 xi (1 ≤ i ≤ φ(n)) 与 n 互质，所以 aφ(n)
≡ 1 mod n （消去律）。
欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 n ，小于 n 且和 n 互质的正整数（包括 1）的个数，记作 φ(n) 。
完全余数集合：
定义小于 n 且和 n 互质的数构成的集合为 Zn ，称呼这个集合为 n 的完全余数集合。
显然 |Zn| ＝φ(n) 。
有关性质：
对于素数 p ，φ(p) = p -1 。
对于两个不同素数 p， q ，它们的乘积 n = p * q 满足 φ(n) = (p -1) * (q -1) 。
这是因为 Zn = {1, 2, 3, ..., n{p, 2p, ..., (q{q, 2q, ..., (p1)1)1) = (p -1) * (q -1) ＝φ(p) * φ(q) 。
消去律：如果 gcd(c,p) = 1 ，则 ac ≡ bc mod p ⇒ a ≡ b mod p
调和级数S=1+1/2+1/3+……是发散的，证明如下：
由于ln(1+1/n)
于是调和级数的前n项部分和满足
Sn=1+1/2+1/3+…+1/n>ln(1+1)+ln(1+1/2)+ln(1+1/3)+…+ln(1+1/n)
=ln2+ln(3/2)+ln(4/3)+…+ln[(n+1)/n]
=ln[2*3/2*4/3*…*(n+1)/n]=ln(n+1)
由于
lim Sn（n→∞）≥lim ln(n+1)（n→∞）=+∞
所以Sn的极限不存在，调和级数发散。
但极限S=lim[1+1/2+1/3+…+1/n-ln(n)]（n→∞）却存在，因为Sn=1+1/2+1/3+…+1/n-ln(n)>ln(1+1)+ln(1+1/2)+ln(1+1/3)+…+ln(1+1/n)-ln(n)
=ln(n+1)-ln(n)=ln(1+1/n)
由于
lim Sn（n→∞）≥lim ln(1+1/n)（n→∞）=0
因此Sn有下界
而
Sn-S(n+1)=1+1/2+1/3+…+1/n-ln(n)-[1+1/2+1/3+…+1/(n+1)-ln(n+1)]
=ln(n+1)-ln(n)-1/(n+1)=ln(1+1/n)-1/(n+1)
将ln(1+1/n)展开，取其前两项，由于舍弃的项之和大于0，故
ln(1+1/n)-1/(n+1)>1/n-1/(2n^2)-1/(n+1)=1/(n^2+n)-1/(2n^2)>0
即ln(1+1/n)-1/(n+1)>0，所以Sn单调递减。由单调有界数列极限定理，可知Sn必有极限，因此
S=lim[1+1/2+1/3+…+1/n-ln(n)]（n→∞）存在。
于是设这个数为γ，这个数就叫作欧拉常数，他的近似值约为0.57721566490153286060651209，目前还不知道它是有理数还是无理数。在微积分学中，欧拉常数γ有许多应用，如求某些数列的极限，某些收敛数项级数的和等。例如求
lim[1/(n+1)+1/(n+2)+…+1/(n+n)]（n→∞），可以这样做：lim[1/(n+1)+1/(n+2)+…+1/(n+n)]（n→∞）
=lim[1+1/2+1/3+…+1/(n+n)-ln(n+n)]（n→∞）
-lim[1+1/2+1/3+…+1/n-ln(n)]（n→∞）+lim[ln(n+n)-ln(n)]（n→∞）=γ-γ+ln2=ln2
欧拉常数发现的历史
著名数学家莱昂哈德·欧拉(1707-1783)该常数最先由瑞士数学家莱昂哈德·欧拉(Leonhard Euler)在1735年发表的文章 De
Progreionibus harmonicus observationes 中定义。欧拉曾经使用C作为它的符号，并计算出了它的前6位小数。
公式证明（共11篇）
欧洲签证在职证明（共7篇）
证明函格式
欧式家具特点
遗失证明格式