什麼是歐拉函數？
歐拉函數記作 \(\varphi(n)\)，用來計算在 1 到 n 之間，有多少個正整數和 n 的最大公因數為 1，也就是與 n 互質的整數個數。舉例來說，\(\varphi(9) = 6\)，因為 1、2、4、5、7、8 這六個數都與 9 互質。歐拉函數是數論中的核心概念，也廣泛應用於密碼學領域；其中最著名的就是 RSA 演算法——\(\varphi(n)\) 決定了產生金鑰時所需的模反元素。
如何使用本計算機
輸入任一正整數 n，再按下計算即可。本工具會將 n 分解為各個相異質因數，並套用乘積公式，瞬間算出 \(\varphi(n)\)，同時列出找到的所有相異質數。無論是小數字還是高達十億的大數字都能輕鬆處理。
公式詳解
計算歐拉函數最有效率的方式是使用乘積公式：
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$其中乘積取遍所有整除 n 的相異質數 \(p\)。
你只需要用到相異的質數，不必管它出現幾次。每一個 \(\left(1 - \frac{1}{p}\right)\) 因子都會剔除掉能被該質數整除的那一部分數字。
計算範例
以 \(n = 36\) 為例，它的質因數分解為 \(2^2 \times 3^2\)，因此相異質數為 2 和 3。於是：
$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$
所以在 1 到 36 之間，恰好有 12 個整數與 36 互質。
常見問題
\(\varphi(1)\) 等於多少？依照慣例，\(\varphi(1) = 1\)，因為 1 與自己互質。
質數 p 的歐拉函數是多少？對任何質數 \(p\) 而言，\(\varphi(p) = p - 1\)，因為從 1 到 \(p-1\) 的每一個整數都與 \(p\) 互質。
歐拉函數具有積性嗎？是的。若 \(\gcd(a, b) = 1\)，則 \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\)；這正是為什麼可以用相異質數的乘積來計算的原因。
