標籤: 暫無標籤

在數論,對正整數n,歐拉函數是少於或等於n的數中與n互質的數的數目。此函數以其首名研究者歐拉命名,它又稱為Euler's totient function、φ函數、歐拉商數等。 例如φ(8)=4,因為1,3,5,7均和8互質。 從歐拉函數引伸出來在環論方面的事實和拉格朗日定理構成了歐拉定理的證明。

1 歐拉函數 -概述

在數論,對正整數n,歐拉函數varphi(n)是少於或等於n的數中與n互質的數的數目。此函數以其首名研究者歐拉命名,它又稱為Euler's totient function、φ函數、歐拉商數等。

例如varphi(8)=4,因為1,3,5,7均和8互質。

從歐拉函數引伸出來在環論方面的事實和拉格朗日定理構成了歐拉定理的證明。

2 歐拉函數 -φ函數的值



<math>\varphi(1)=1</math>(唯一和1互質的數就是1本身)。

若n是質數p的k次冪,<math>\varphi(n)=p^a-p^=(p-1)p^</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\right)</math>。

例如<math>\varphi(72)=\varphi(2^3\times3^2)=2^(2-1)\times3^(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^ \equiv 1 \pmod p</math>

即費馬小定理。
上一篇[小行星2002]    下一篇 [皮埃爾·布格]

相關評論

同義詞:暫無同義詞