歐拉定理是什麽東西
在數學及許多分支中都可以見到很多以歐拉命名的常數、公式和定理。在數論中，歐拉定理(Euler Theorem，也稱費馬-歐拉定理或歐拉函數定理)是壹個關於同余的性質。歐拉定理得名於瑞士數學家萊昂哈德·歐拉，該定理被認為是數學世界中最美妙的定理之壹。歐拉定理實際上是費馬小定理的推廣。此外還有平面幾何中的歐拉定理、多面體歐拉定理(在壹凸多面體中，頂點數-棱邊數+面數=2)。西方經濟學中歐拉定理又稱為產量分配凈盡定理，指在完全競爭的條件下，假設長期中規模收益不變，則全部產品正好足夠分配給各個要素。另有歐拉公式。
內容
在數論中，歐拉定理,(也稱費馬-歐拉定理)是壹個關於同余的性質。歐拉定理表明，若n,a為正整數，且n,a互質，則:
歐拉定理
折疊 證明
將1~n中與n互質的數按順序排布:x1,x2……xφ(n) (顯然，***有φ(n)個數)
我們考慮這麽壹些數:
m1=a*x1;m2=a*x2;m3=a*x3……mφ(n)=a*xφ(n)
1)這些數中的任意兩個都不模n同余，因為如果有mS≡mR (mod n) (這裏假定mS更大壹些)，就有:
mS-mR=a(xS-xR)=qn，即n能整除a(xS-xR)。但是a與n互質，a與n的最大公因子是1，而xS-xR<n，因而左式不可能被n整除。也就是說這些數中的任意兩個都不模n同余，φ(n)個數有φ(n)種余數。
2)這些數除n的余數都與n互質，因為如果余數與n有公因子r，那麽a*xi=pn+qr=r(……)，a*xi與n不互質，而這是不可能的。那麽這些數除n的余數，都在x1,x2,x3……xφ(n)中，因為這是1~n中與n互質的所有數，而余數又小於n.
由1)和2)可知，數m1,m2,m3……mφ(n)(如果將其次序重新排列)必須相應地同余於x1,x2,x3……xφ(n).
故得出:m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)
或者說a^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n)
或者為了方便:K{a^[φ(n)]-1}≡0 ( mod n ) 這裏K=x1*x2*x3……xφ(n)。
可知K{a^[φ(n)]-1}被n整除。但K中的因子x1,x2……都與n互質，所以K與n互質。那麽a^[φ(n)]-1必須能被n整除，即a^[φ(n)]-1≡0 (mod n)，即a^[φ(n)]≡1 (mod n)，得證。
費馬小定理:
a是不能被質數p整除的正整數，則有a^(p-1) ≡ 1 (mod p)
證明這個定理非常簡單，由於p是質數，所以有φ(p) = p-1，代入歐拉定理即可證明。推論:對於任意正整數a，有a^p ≡ a (mod p)，因為a能被p整除時結論顯然成立。
折疊 應用
首先看壹個基本的例子。令a
= 3，n =
5，這兩個數是互素的。比5小的正整數中與5互素的數有1、2、3和4，所以φ(5)=4(詳情見[歐拉函數])。計算:a^{φ(n)} = 3^4
=81，而81= 80 + 1 Ξ 1 (mod 5)。與定理結果相符。
這個定理可以用來簡化冪的模運算。比如計算7^{222}的個位數，實際是求7^{222}被10除的余數。7和10[[互素]]，且φ(10)=4。由歐拉定理知7^4Ξ1(mod
10)。所以7^{222}=(7^4)^55*(7^2)Ξ1^{55}*7^2Ξ49Ξ9 (mod 10)。