Euler函式

初等數論的歐拉函式 歐拉φ函式：φ(n 互素的整數的個數。n

Euler函式

歐拉(Euler)函式通常是指下面這個：
初等數論的歐拉函式
歐拉φ函式：φ(n)是所有小於n的正整數里，和n互素的整數的個數。n是一個正整數。
歐拉證明了下面這個式子：
如果n的標準素因子分解式是p1^a1*p2^a2*……*pm^am，其中眾pj(j=1,2,……,m)都是素數，而且兩兩不等。則有
φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)
利用容斥原理可以證明它。
關於Euler函式的一個著名定理:
a、n都是正整數，並且n>1，(a,n)=1，則有a^φ(n)-1≡0(mod n),這個是同餘的表達式。另外還可以寫成：n|[a^φ(n)-1]，即n是a^φ(n)-1的因子的意思。