欧拉公式证明

欧拉公式证明第1篇：欧拉函数公式及其证明

欧拉函数：

欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数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)

≡1modn

。

证明：

(1)令Zn={x1,x2,...,xφ(n)}，S={a*x1modn,a*x2modn,...,a*xφ(n)modn}，

则Zn=S。

①因为a与n互质，xi(1≤i≤φ(n))与n互质，所以a*xi

与n互质，所以a*xi

modn∈Zn。

②若i≠j，那么xi≠xj，且由a,n互质可得a*ximodn≠a*xjmodn（消去律）。

(2)

a*x1*x2*...*xφ(n)modn

≡(a*x1)*(a*x2)*...*(a*xφ(n))modn

≡(a*x1modn)*(a*x2modn)*...*(a*xφ(n)modn)modn

≡

x1*x2*...*xφ(n)modn

φ(n)

对比等式的左右两端，因为xi

(1≤i≤φ(n))与n互质，所以a

≡

1modn（消去律）。注：

消去律：如果gcd(c,p)=1，则ac≡bcmodp?a≡bmodp。

费马定理：

若正整数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是偶数。

//直接求解欧拉函数

inteuler(intn){//返回euler(n)

intres=n,a=n;

for(inti=2;i*iif(a%i==0){

res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出

while(a%i==0)a/=i;

}

}

if(a>1)res=res/a*(a-1);

returnres;}

//筛选法打欧拉函数表

#defineMax1000001inteuler[Max];voidInit(){

euler[1]=1;

for(inti=2;ieuler[i]=i;

for(inti=2;iif(euler[i]==i)

for(intj=i;jeuler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出

}

第2篇：证明欧拉定理

证明：

(1)令Zn={x1,x2,...,xφ(n)}，S={a*x1modn,a*x2modn,...,a*xφ(n)modn}，

则Zn=S。

#①因为a与n互质，xi(1≤i≤φ(n))与n互质，所以a*xi与n互质，所以a*ximodn∈Zn。

#②若i≠j，那么xi≠xj，且由a,n互质可得a*ximodn≠a*xjmodn（消去律）。

(2)aφ(n)*x1*x2*...*xφ(n)modn

≡(a*x1)*(a*x2)*...*(a*xφ(n))modn≡(a*x1modn)*(a*x2modn)*...*(a*xφ(n)modn)modn≡x1*x2*...*xφ(n)modn对比等式的左右两端，因为xi(1≤i≤φ(n))与n互质，所以aφ(n)

≡1modn（消去律）。

欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数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≡bcmodp?a≡bmodp

第3篇：欧拉常数的证明

调和级数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)

由于

limSn（n→∞）≥limln(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)

由于

limSn（n→∞）≥limln(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单调递减。由单