证明：
(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
第2篇：欧拉定理
欧拉定理
欧拉定理
认识欧拉
欧拉，瑞士数学家，13岁进巴塞尔大学读书，得到著名数学家贝努利的精心指导．欧拉是科学史上最多产的一位杰出的数学家，他从19岁开始发表论文，直到76岁，他那不倦的一生，共写下了886本书籍和论文，其中在世时发表了700多篇论文。彼得堡科学院为了整理他的著作，整整用了47年。欧拉著作惊人的高产并不是偶然的。他那顽强的毅力和孜孜不倦的治学精神，可以使他在任何不良的环境中工作：他常常抱着孩子在膝盖上完成论文。即使在他双目失明后的17年间，也没有停止对数学的研究，口述了好几本书和400余
篇的论文。当他写出了计算天王星轨道的计算要领后离开了人世。欧拉永远是我们可敬的老师。欧拉研究论著几乎涉及到所有数学分支，对物理力学、天文学、弹道学、航海学、建筑学、音乐都有研究！有许多公式、定理、解法、函数、方程、常数等是以欧拉名字命名的。欧拉写的数学教材在当时一直被当作标准教程。19世纪伟大的数学家高斯（Gau，1777-1855）曾说过“研究欧拉的著作永远是了解数学的最好方法”。欧拉还是数学符号发明者，他创设的许多数学符号，例如π，i，e，sin，cos，tg，Σ，f(x)等等，至今沿用。欧拉不仅解决了彗星轨迹的计算问题，还解决了使牛顿头痛的月离问题。对著名的“哥尼斯堡七桥问题”的完美解答开创了“图论”的研究。欧拉发现，不论什么形状的凸多面体，其顶点数V、棱数E、面数F之间总有关系V+F-E=2，此式称为欧拉公式。V+F-E即欧拉示性数，已成为“拓扑学”的基础概念。那么什么是“拓扑学”？ 欧拉是如何发现这个关系的？他是用什么方法研究的？今天让我们沿着欧拉的足
迹，怀着崇敬的心情和欣赏的态度探索这个公式......初等数论中的欧拉定理
定理内容
在数论中，欧拉定理（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互素，(a,n)= 1，则
a^φ(n)≡ 1(mod n)
证明
首先证明下面这个命题：
对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不大于n且与n互素的数，即n的一个化简剩余系，或称简系，或称缩系)，考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)}
则S = Zn
1)由于a,n互质，xi也与n互质，则a*xi也一定于p互质，因此
任意xi，a*xi(mod n)必然是Zn的一个元素
2)对于Zn中两个元素xi和xj，如果xi ≠ xj
则a*xi(mod n)≠ a*xi(mod n)，这个由a、p互质和消去律可以得出。
所以，很明显，S=Zn
既然这样，那么
（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)
考虑上面等式左边和右边
左边等于(a*（x1 × x2 ×...× xφ(n)）)(mod n)
右边等于x1 × x2 ×...× xφ(n)）(mod n)
而x1 × x2 ×...× xφ(n)(mod n)和n互质
根据消去律，可以从等式两边约去，就得到：
a^φ(n)≡ 1(mod n)
推论：对于互质的数a、n，满足a^(φ(n)+1)≡ a(mod n)
费马定理:
a是不能被质数p整除的正整数，则有a^(p-1)≡ 1(mod p)
证明这个定理非常简单，由于φ(p)= p-1，代入欧拉定理即可证明。
同样有推论：对于不能被质数p整除的正整数a，有a^p ≡ a(mod p)
平面几何里的欧拉定理
定理内容
设三角形的外接圆半径为R，内切圆半径为r，外心与内心的距离为d，则d^2=R^2-2Rr．
证明
O、I分别为⊿ABC的外心与内心．
连AI并延长交⊙O于点D，由AI平分ÐBAC，故D为弧BC的中点．
连DO并延长交⊙O于E，则DE为与BC垂直的⊙O的直径．
由圆幂定理知，R2-d2=(R+d)(R-d)=IA·ID．（作直线OI与⊙O交于两点，即可用证明）
但DB=DI（可连BI，证明ÐDBI=ÐDIB得），故只需证2Rr=IA·DB，即2R∶DB=IA∶r 即可．
而这个比例式可由⊿AFI∽⊿EBD证得．故得R2-d2=2Rr，即证．
拓扑学里的欧拉公式
V+F-E=X(P)，V是多面体P的顶点个数，F是多面体P的面数，E是多面体P的棱的条数,X(P)是多面体P的欧拉示性数。
如果P可以同胚于一个球面（可以通俗地理解为能吹胀成一个球面），那么X(P)=2，如果P同胚于一个接有h个环柄的球面，那么X(P)=2-2h。
X(P)叫做P的拓扑不变量，是拓扑学研究的范围。
V+F-E=2的证明
方法1：（利用几何画板）
逐步减少多面体的棱数，分析V+F-E
先以简单的四面体ABCD为例分析证法。
去掉一个面，使它变为平面图形，四面体顶点数V、棱数E与剩下的面数F1变形后都没有变。因此，要研究V、E和F关系，只需去掉一个面变为平面图形，证V+F1-E=1
（1）去掉一条棱，就减少一个面，V+F1-E不变。依次去掉所有的面，变为“树枝形”。
（2）从剩下的树枝形中，每去掉一条棱，就减少一个顶点，V+F1-E不变，直至只剩下一条棱。
以上过程V+F1-E不变，V+F1-E=1，所以加上去掉的一个面，V+F-E =2。
对任意的简单多面体，运用这样的方法，都是只剩下一条线段。因此公式对任意简单多面体都是正确的。
方法2：计算多面体各面内角和
设多面体顶点数V，面数F，棱数E。剪掉一个面，使它变为平面图形（拉开图）,求所有面内角总和Σα
一方面，在原图中利用各面求内角总和。
设有F个面，各面的边数为n1,n2，…，nF，各面内角总和为：
Σα = [(n1-2)·180度+(n2-2)·180度+…+(nF-2)·180度]
=(n1+n2+…+nF-2F)·180度
=(2E-2F)·180度 =(E-F)·360度（1）
另一方面，在拉开图中利用顶点求内角总和。
设剪去的一个面为n边形，其内角和为(n-2)·180角，则所有V个顶点中，有n个顶点在边上，V-n个顶点在中间。中间V-n个顶点处的内角和为(V-n)·360度，边上的n个顶点处的内角和(n-2)·180度。
所以，多面体各面的内角总和：
Σα =(V-n)·360度+(n-2)·180度+(n-2)·180度
=（V-2）·360度（2）
由(1)(2)得：(E-F)·360度=（V-2）·360度
所以 V+F-E=2.方法3 用拓朴学方法证明欧拉公式
图
尝试一下用拓朴学方法证明关于多面体的面、棱、顶点数的欧拉公式。
欧拉公式：对于任意多面体（即各面都是平面多边形并且没有洞的立体），假设F，E和V分别表示面，棱（或边），角（或顶）的个数，那末
F-E+V=2。
证明 如图（图是立方体，但证明是一般的，是“拓朴”的）：
（1）把多面体（图中①）看成表面是薄橡皮的中空立体。
（2）去掉多面体的一个面，就可以完全拉开铺在平面上而得到一个平面中的直线形，像图中②的样子。假设F′，E′和V′分别表示这
个平面图形的（简单）多边形、边和顶点的个数，我们只须证明F′-E′+V′=1。
（3）对于这个平面图形，进行三角形分割，也就是说，对于还不是三角形的多边形陆续引进对角线，一直到成为一些三角形为止，像图中③的样子。每引进一条对角线，F′和E′各增加1，而V′却不变，所以F′-E′+V′不变。因此当完全分割成三角形的时候，F′-E′+V′的值仍然没有变。有些三角形有一边或两边在平面图形的边界上。
（4）如果某一个三角形有一边在边界上，例如图④中的△ABC，去掉这个三角形的不属于其他三角形的边，即AC，这样也就去掉了△ABC。这样F′和E′各减去1而V′不变，所以F′-E′+V′也没有变。
（5）如果某一个三角形有二边在边界上，例如图⑤中的△DEF，去掉这个三角形的不属于其他三角形的边，即DF和EF，这样就去掉△DEF。这样F′减去1，E′减去2，V′减去1，因此F′-E′+V′仍没有变。
（6）这样继续进行，直到只剩下一个三角形为止，像图中⑥的样子。这时F′=1，E′=3，V′=3，因此F′-E′+V′=1-3+3=1。
（7）因为原来图形是连在一起的，中间引进的各种变化也不破坏这事实，因此最后图形还是连在一起的，所以最后不会是分散在向外的几个三角形，像图中⑦那样。
（8）如果最后是像图中⑧的样子，我们可以去掉其中的一个三角形，也就是去掉1个三角形，3个边和2个顶点。因此F′-E′+V′仍然没有变。
即F′-E′+V′=1
成立，于是欧拉公式：
F-E+V=2
得证。
复变函数论里的欧拉公式
定理内容
e^ix=cosx+isinx
e是自然对数的底，i是虚数单位。
它将三角函数的定义域扩大到复数，建立了三角函数和指数函数的关系，它在复变函数论里占有非常重要的地位。
将公式里的x换成-x，得到：
e^-ix=cosx-isinx，然后采用两式相加减的方法得到：
sinx=(e^ix-e^-ix)/(2i)，cosx=(e^ix+e^-ix)/2.这两个也叫做欧拉公式。
“上帝创造的公式”
将e^ix=cosx+isinx中的x取作∏就得到：
e^i∏+1=0.这个恒等式也叫做欧拉公式，它是数学里最令人着迷的一个公式，它将数学里最重要的几个数学联系到了一起：两个超越数：自然对数的底e，圆周率∏，两个单位：虚数单位i和自然数的单位1，以及数学里常见的0。数学家们评价它是“上帝创造的公式”，我们只能看它而不能理解它。
欧拉定理的运用方法
（1）分式：
a＾r/(a-b)(a-c)+b＾r/(b-c)(b-a)+c＾r/(c-a)(c-b)
当r=0,1时式子的值为0
当r=2时值为1
当r=3时值为a+b+c
（2）复数
由e＾iθ=cosθ+isinθ,得到：
sinθ=（e＾iθ-e＾-iθ）/2i
cosθ=（e＾iθ+e＾-iθ）/2
（3）三角形
设R为三角形外接圆半径，r为内切圆半径，d为外心到内心的距离，则：
d＾2=R＾2-2Rr
（4）多面体
设v为顶点数，e为棱数，f是面数，则
v-e+f=2-2p
p为欧拉示性数，例如
p=0 的多面体叫第零类多面体
p=1 的多面体叫第一类多面体
(5)多边形
设一个二维几何图形的顶点数为V，划分区域数为Ar，一笔画笔数为B,则有：
V+Ar-B=1
(如：矩形加上两条对角线所组成的图形，V=5,Ar=4,B=8)
(6).欧拉定理
在同一个三角形中，它的外心Circumcenter、重心Gravity、九点圆圆心Nine-point-center、垂心Orthocenter共线。
其实欧拉公式是有很多的，上面仅是几个常用的。
使用欧拉定理计算足球五边形和六边形数
问：足球表面由五边型和六边型的皮革拼成，计算一共有多少个这样的五边型和六边型？
答：足球是多面体，满足欧拉公式F－E＋V＝2，其中F,E,V分别表示面,棱,顶点的个数
设足球表面正五边形(黑皮子)和正六边形(白皮子)的面各有x个和y个，那么
面数F＝x＋y
棱数E＝(5x+6y)/2（每条棱由两块皮子共用）
顶点数V＝(5x+6y)/3（每个顶点由三块皮子共用）
由欧拉公式，x＋y－(5x+6y)/2＋(5x+6y)/3＝2，解得x＝12。所以，共有12块黑皮子
所以，黑皮子一共有12×5＝60条棱，这60条棱都是与白皮子缝合在一起的对于白皮子来说：每块白色皮子的6条边中，有3条边与黑色皮子的边缝在一起，另3条边则与其它白色皮子的边缝在一起。
所以白皮子所有边的一半是与黑皮子缝合在一起的那么白皮子就应该一共有60×2＝120条边，120÷6＝20
所以共有20块白皮子
（或者，每一个六边形的六条边都与其它的三个六边形的三条边和三个五边形的三条边连接；每一个五边形的五条边都与其它的五个六边形的五条边连接
所以，五边形的个数x=3y/5。
之前求得x=12，所以y=20）
经济学中的“欧拉定理”
在西方经济学里，产量和生产要素L、K的关系表述为Q＝Q(L，K)，如果具体的函数形式是一次齐次的，那么就有：Q＝L(ðQ/ðL)＋K(ðQ/ðK)，换句话说，产
品分配净尽取决于Q能否表示为一个一次齐次函数形式。
因为ðQ/ðL＝MPL＝w/P被视为劳动对产量的贡献，ðQ/ðK＝MPK＝r/P被视为资本对产量的贡献，因此，此式被解释为“产品分配净尽定理”，也就是所有产品都被所有的要素恰好分配完而没有剩余。因为形式上符合数学欧拉定理，所以称为欧拉定理。
【同余理论中的"欧拉定理"】
设a,m∈N,(a,m)=1,则a^(f(m))≡1(mod m)
(注:f(m)指模m的简系个数)
欧拉定理的意义
（1）数学规律：公式描述了简单多面体中顶点数、面数、棱数之间特有的规律
（2）思想方法创新：定理发现证明过程中，观念上，假设它的表面是橡皮薄膜制成的，可随意拉伸；方法上将底面剪掉，化为平面图形（立体图→平面拉开图）。
（3）引入拓扑学：从立体图到拉开图，各面的形状、长度、距离、面积等与度量有关的量发生了变化，而顶点数，面数，棱数等不变。
定理引导我们进入一个新几何学领域：拓扑学。我们用一种可随意变形但不得撕破或粘连的材料（如橡皮波）做成的图形，拓扑学就是研究图形在这种变形过程中的不变的性质。
（4）提出多面体分类方法：
在欧拉公式中，f(p)=V+F-E 叫做欧拉示性数。欧拉定理告诉我们，简单多面体f(p)=2。
除简单多面体外，还有非简单多面体。例如，将长方体挖去一个洞，连结底面相应顶点得到的多面体。它的表面不能经过连续变形变为一个球面，而能变为一个环面。其欧拉示性数f(p)=16+16-32=0，即带一个洞的多面体的欧拉示性数为0。
（5）利用欧拉定理可解决一些实际问题
如：为什么正多面体只有5种？ 足球与C60的关系？否有棱数为7的正多面体？等
第3篇：欧拉定理
欧拉定理
欧拉定理（Euler Theorem），也称费马-欧拉定理或欧拉函数定理
[编辑] 什么是欧拉定理
欧拉定理指出：如果产品市场和要素市场都是完全竞争的，而且厂商生产的规模报酬不变，那么在市场均衡的条件下，所有生产要素实际所取得的报酬总量正好等于社会所生产的总产品。该定理又叫做边际生产力分配理论，还被称为产品分配净尽定理。如上所述，要素的价格是由于要素的市场供给和市场需求共同决定。在完全竞争的条件下，厂商和消费者都被动地接受市场形成的价格。现在的问题是：要素所有者按照市场形成的要素价格获得收入，全部要素收入是否等于社会总产品？
在完全竞争的条件下，厂商使用要素的原则是：要素的边际产品价值等于要素价格。即：
（9.9）
（9.10）
由式9.9和9.10可得：
（9.11）
（9.12）
P为产品的价格，W/P和r/P分别表示了劳动和资本的实际报酬。因此在完全竞争的条件下，单位劳动、单位资本的实际报酬分别等于劳动、资本的边际产量。假定整个社会的劳动总量和资本总量为L和K，而社会总产品为Q，那么就有：
（9.13）
式9.13称为欧拉分配定理。它是由于该定理的证明使用了数学上的欧拉定理而得名。
[编辑] 欧拉定理的证明
假设生产函数为：Q=f(L.K)
由于规模报酬不变，所以生产函数为齐次方程，因此有：
k为人均资本，Q/L为人均产量，人均产量是人均资本k的函数。
由上面两式，即可证明欧拉定理：
在规模报酬递增情况下，如果按照边际生产力分配，则产品不够分配给各个生产要素，即：
（9.14）
在规模报酬递减情况下，如果按边际生产力进行分配，则产品在分配给各个生产要素之后还有剩余，即：
（9.15）
证明如下：
如果生产函数 Q=f(L,K)为r齐次，则有：
因此有：
显然在规模报酬递增时，r>1，所以有：
在规模报酬递减时，所以有：
第4篇：欧拉常数的证明
调和级数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.5772***86060651209，目前还不知道它是有理数还是无理数。在微积分学中，欧拉常数γ有许多应用，如求某些数列的极限，某些收敛数项级数的和等。例如求
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位小数。
第5篇：欧拉函数公式及其证明
欧拉函数 ：
欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 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);//先进行除法是为了防止中间数据的溢出
}
第6篇：欧拉公式的证明
,.欧拉公式的证明
著名的欧拉公式e^(iθ)=cosθ+isinθ是人们公认的优美公式。原因是指数函数和三角函数在实数域中几乎没有什么联系，而在复数域中却发现了他们可以相互转化，并被一个非常简单的关系式联系在一起。特别是当θ=π时，欧拉公式便写成了e^(iπ)+1=0,就这个等式将数中最富有特色的五个数0，1，i , e , π ,绝妙地联系在一起
方法一：用幂级数展开形式证明，但这只是形式证明（严格的说，在实函数域带着i只是形式上的）
再抄一遍：
设z = x+iy 这样 e^z = e^(x+iy)=e^x*e^(iy),就是e^z/e^x = e^(iy)用牛顿幂级数展开式
e^x = 1+x+x^2/2!+x^3/3!+.....+x^n/n!+......把 e^(iy)展开，就得到 e^z/e^x = e^(iy)=1+iy-y^2/2!-iy^3/3!+y^4/4!+iy^5/5!-y^6/6!-.....=(1-y^2/2!+y^4/4!-y^6/6!+.....)+i(y-y^3/3!+y^5/5!-....)由于 cosy = 1-y^2/2!+y^4/4!-y^6/6!+....., siny = y-y^3/3!+y^5/5!-....所以 e^(x+iy)=e^x*e^(iy)=e^x*(cosy+isiny)即 e^(iy)=(cosy+isiny)
方法二：见复变函数第2章，在整个负数域内重新定义了sinz cosz而后根据关系推导出了欧拉公式。着个才是根基。由来缘于此。
方法一是不严格的。
再 请看这2个积分
∫sqrt(x^2-1)dx=x*sqrt(x^2-1)/2-ln(2*sqrt(x^2-1)+2x)/2 ∫sqrt(1-x^2)dx=arcsin(x)/2+x*sqrt(1-x^2)/2;上式左边相当于下式左边乘以i 于是上式右边相当于下式右边乘以i 然后化简就得到欧拉公式
这个证明方法不太严密
但很有启发性
历史上先是有人用上述方法得到了对数函数和反三角函数的关系
然后被欧拉看到了,才得到了欧拉公式 设a t θ ЄR,ρЄR+,a^(it)Єz有: a^(it)=ρ(cosθ+isinθ)1
因共轭解适合方程,用-i替换i有: a^(-it)=ρ(cosθ-isinθ)2
;..,.由1,2得ρ=1,点P[a^(it)]在单位圆上,a^(it)可表达为: a^(it)=cosθ+isinθ 3 设t=u(θ),对3微商有:
[a^(it)]*(lna)*u'(θ)*i=-sinθ+icosθ 整理有:
[a^(it)]*(lna)*u'(θ)*i=(cosθ+isinθ)(cosπ/2+isinπ/2)约去a^(it)有: u'(θ)=logae 4 4取积分有: T=(logae)*θ+Ψ 5
θ→0时,t=limt=Ψ,带入3有: a^(iΨ)=1 即: Ψ=0 6
6代入5有: T=(logae)*θ 7 7代入3有:
[a^(logae)]^(iθ)=cosθ+isinθ 化简得欧拉公式: e^(iθ)=cosθ+isinθ
（后两者才是真正让我震惊的！！）
;..
第7篇：.12.15初等数论费马小定理与欧拉定理
第七讲
费马小定理与欧拉定理
2017.12.18 基础例题
1.设n是自然数，则5
2.设{x1，x2，x3，…，xm}为模m的一个简化剩余系，则x1x2x3
3.设a，b，c，m为自然数，m>1，(b，m)=1，且ba记da,c，则bd|1234nnnn
xm1mod
1modm，bc1modm，1modm
4.设p是素数，p|bn-1，n为自然数，则下列两个结论中至少有一个成立：
(1)p|bd-1对于某个因数d
(2)p1modn
5.将211-1=2047分解质因数
6.将612-1分解质因数
7.若a，b是任意整数，p为素数.证明：abpapbpmodp
8.设p为奇素数，a，n都是正整数，且pn|ap-1.
(1)证明：pn-1|a-1；
(2)当p=2时，上述结论成立吗?
10.求(1237156+34)28被111除的余数.
11.设p是一个大于5的素数，求证：240|p4-1
12.设p为素数.证明：存在无穷多个正整数n使得2nnmodp
13.(1)证明下列事实但不许用费马小定理：若p是质数，h1，h2，…，hn是整数，则(h1+h2+…+hn)p≡h1p+h2p+…+hnp(modp)
(2)由(1)证明费马定理，然后再由费马定理证明欧拉定理.每周真题小练
1.(ELMO2017)设H为三角形ABC的垂心，M为边BC的中点.以AH为直径的圆上，有相异的两点P，Q(P、Q两点均不与A重合)，满足M位于直线PQ上.证明：三角形APQ的垂心位于三角形ABC的外接圆上.
an是1，2.(命题人讲座)设n是一个大于1的奇数，数a1，a2，a3，…，2，3，…，nn中与n互素的所有正整数.证明k1cosakn12n
