最终幻想王者之剑日文:请问欧拉函数是个什么函数

在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。

设φ为欧拉函数
φ（n）=与n互质的数的个数

欧拉函数
易维基，关注传统文化、神秘文化以及高新科技的自由百科全书
在数论，对正整数n，欧拉函数<math>\varphi(n)</math>是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。

例如<math>\varphi(8)=4</math>，因为1,3,5,7均和8互质。

从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

[编辑]φ函数的值
<math>\varphi(1)=1</math>（唯一和1互质的数就是1本身）。

若n是质数p的k次幂，<math>\varphi(n)=p^a-p^{a-1}=(p-1)p^{k-1}</math>，因为除了p的倍数外，其他数都跟n互质。

欧拉函数是积性函数——若m,n互质，<math>\varphi(mn)=\varphi(m)\varphi(n)</math>。证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，<math>A \times B</math>和C可建立一一对应的关系。因此<math>\varphi(n)</math>的值使用算术基本定理便知，

若<math>n = \prod_{p\mid n} p^{\alpha_p}</math>，
则<math>\varphi(n) = \prod_{p\mid n} p^{\alpha_p-1}(p-1) = n\prod_{p|n}\left(1-\frac{1}{p}\right)</math>。
例如<math>\varphi(72)=\varphi(2^3\times3^2)=2^{3-1}(2-1)\times3^{2-1}(3-1)=2^2\times1\times3\times2=24</math>

[编辑]与欧拉定理、费马小定理的关系
对任何两个互质的正整数a, m，<math>m\ge2</math>，有

<math>a^{\varphi(m)} \equiv 1 \pmod m</math>
即欧拉定理

当m是质数p时，此式则为：

<math>a^{p-1} \equiv 1 \pmod p</math>
即费马小定理。bg:Функция на Ойлер cs:Eulerova funkce de:Eulersche φ-Funktion en:Euler's totient function es:Función fi de Euler fr:Indicatrice d'Euler he:פונקצית אוילר hu:Euler-függvény it:Funzione phi di Eulero ja:オイラーのφ关数 ko:오일러 파이 함수 nl:Indicator van n pl:Funkcja phi pt:Função totiente de Euler sl:Eulerjeva funkcija fi sv:Eulers phi-funktion

取自"http://www.eeeeee.org/wiki/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0"