欧拉函数，记作 \(\varphi(n)\)，是数论中的一个重要函数，它表示小于或等于正整数 \(n\) 的所有正整数中，与 \(n\) 互质的数的个数。互质意味着两个数的最大公约数为1。
欧拉函数的值可以通过以下公式计算：
[
\varphi(n) = n \times \prod_{p \mid n} \left(1 - \frac{1}{p}\right)
]
其中 \(p\) 是 \(n\) 的所有不同的质因数。
例如，要计算 \(\varphi(8)\)，因为8的质因数是2，所以：
[
\varphi(8) = 8 \times \left(1 - \frac{1}{2}\right) = 8 \times \frac{1}{2} = 4
]
这意味着在1到8之间，有4个数(1, 3, 5, 7)与8互质。
欧拉函数有一些重要性质，例如：
-
如果 \(p\) 是质数，则 \(\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)\)
-
如果 \(a\) 和 \(n\) 互质，则 \(\varphi(an) = \varphi(a)\varphi(n)\)
-
特别地，对于任意两个互质的正整数 \(a\) 和 \(n\)(\(n > 2\))，有 \(a^{\varphi(n)} \equiv 1 \pmod{n}\)，这是欧拉定理