什麼是歐拉函數?
歐拉函數記作 \(\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 互質。
更多範例
範例 1:質數,φ(13)
13 是質數,因此它唯一的質因數就是 13 本身:
\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12。這符合質數的簡便公式 \(\varphi(p) = p-1\)。
範例 2:質數冪,φ(32)
分解:\(32 = 2^5\)。唯一的不同質因數是 2。
\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16。
等價的質數冪形式:\(\varphi(p^k) = p^k - p^{k-1}\),因此 \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\)。這些恰好是 1 到 31 之間的所有奇數。
範例 3:三個或更多不同質數,φ(210)
分解:\(210 = 2 \cdot 3 \cdot 5 \cdot 7\)。
- 從 \(210\) 開始。
- 乘以 \(1-\frac{1}{2} = \frac{1}{2}\):\(210 \cdot \frac{1}{2} = 105\)。
- 乘以 \(1-\frac{1}{3} = \frac{2}{3}\):\(105 \cdot \frac{2}{3} = 70\)。
- 乘以 \(1-\frac{1}{5} = \frac{4}{5}\):\(70 \cdot \frac{4}{5} = 56\)。
- 乘以 \(1-\frac{1}{7} = \frac{6}{7}\):\(56 \cdot \frac{6}{7} = 48\)。
因此 \(\varphi(210) = \)48。注意乘積規則中每個不同質數只使用一次。例如 \(60 = 2^2 \cdot 3 \cdot 5\),得到 \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\)。
φ(n) 的解讀與應用
- 與質數的關係:對於 \(n \ge 2\),當且僅當 \(n\) 為質數時 \(\varphi(n) = n-1\)。小於質數的每個數都與它互質。若 \(n\) 為合數,則小於它的數中至少有一個與它有公因數,因此 \(\varphi(n) < n-1\)。
- 單位群:\(\varphi(n)\) 是模 \(n\) 的單位群中元素的個數,即模 \(n\) 有乘法反元素的剩餘類。對於 \(n = 15\),這些是 1、2、4、7、8、11、13、14,共 8 個元素。
- 尤拉定理:若 \(\gcd(a, n) = 1\),則 \(a^{\varphi(n)} \equiv 1 \pmod{n}\)。例如:\(a = 2\),\(n = 15\),\(\varphi(15) = \)8,且 \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\)。費馬小定理是 \(n = p\)(質數)時的特例。
- RSA:當 \(n = pq\),其中 \(p\) 與 \(q\) 為不同質數時,\(\varphi(n) = (p-1)(q-1)\)。若 \(n = 15 = 3 \cdot 5\):\(\varphi(15) = 2 \cdot 4 = 8\)。公開指數 \(e\) 必須與 \(\varphi(n)\) 互質,而私密指數 \(d\) 滿足 \(ed \equiv 1 \pmod{\varphi(n)}\)。實際的 RSA 使用的質數有數百位數字。任何能夠分解 \(n\) 的人都能計算 \(\varphi(n)\),這也是安全性依賴於分解困難的原因。
- 比值只取決於不同的質數:\(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\)。指數無關緊要。例如,6 與 12 的質因數集合都是 {2, 3},因此 \(\varphi(6)/6 = 2/6 = 1/3\),\(\varphi(12)/12 = 4/12 = 1/3\)。
常見問題
\(\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)\);這正是為什麼可以用相異質數的乘積來計算的原因。