在数论中，欧拉函数是很重要的一个函数，此函数以欧拉本人的名字命名，又称为φ函数、欧拉商数。

例如整数8，小于8且和8互质的正整数有：1、3、5、7，因此
φ(8) = 4。

那么欧拉函数的计算公式是什么，这里将分不同情境给出具体公式。

在此之前先引入一个概念，完全余数集合

很明显，素数 p和小于它的正整数均互质，而小于 p的正整数有 p-1个。
这里用反证法
假设 q < p，且 p和 q不互质 则 p和 q存在公约数为r，r > 1
那么 p = kr
这和p是素数矛盾，因此原公式成立。

小于 p^k的正整数一共有 p^k - 1个
而和 p^k不互质的正整数集合为：
{1p，2p，3p，···， mp}，共有m个
而mp = p^k - p
导出m = p^k-1 - 1
因此欧拉函数的值为
所有小于 p^k的个数减去和 p^k不互质的正整数个数
φ(p^k) = p^k - 1 - m
φ(p^k) = p^k - 1 - （p^k-1 - 1）
φ(p^k) = p^k - p^k-1

因为 n = pq， gcd(p,q) = 1
根据中国余数定理，有
Zn 和 Zp × Zq 之间存在一一映射
所以 n的完全余数集合的元素个数等于集合 Zp与 Zq的元素个数乘积。
即φ(pq) = φ(p)φ(q)

根据以上的知识，我们可以得到对于任意一个正整数 n的欧拉函数。

任意正整数 n可以表示成：
n = p₁^k₁ p₂^k₂ ··· p_i-1^k_i-1 p_i^k_i
这里p₁，p₂，···，p_i为互质的素数

那么
n = p₁^k₁ （p₂^k₂ ··· p_i-1^k_i-1 p_i^k_i）
p₁^k₁ 和 p₂^k₂ ··· p_i-1^k_i-1 p_i^k_i互质

根据定理两个互质正整数 p q，φ(pq) = φ(p)φ(q)得到
φ(n) = φ(p₁^k₁) φ(p₂^k₂ ··· p_i-1^k_i-1 p_i^k_i）

同理，继续分解
φ(n) = φ(p₁^k₁) φ(p₂^k₂） ··· φ(p_i-1^k_i-1） φ(p_i^k_i）

得到
φ(n) = （p₁^k₁ - p₁^k₁-1）（p₂^k₂ - p₂^k₂-1）···（p_i-1^k_i-1 - p_i-1^k_i-1-1）（p_i^k_i - p_i^k_i-1）

φ(n) = p₁^k₁（1 - 1 / p₁）p₂^k₂（1 - 1 / p₂）··· p_i-1^k_i-1（1 - 1 / p_i-1） p_i^k_i（1 - 1 / p_i）

φ(n) = n （1 - 1 / p₁）（1 - 1 / p₂）···（1 - 1 / p_i-1）（1 - 1 / p_i）

至此，欧拉函数证毕。