歐拉函數計算機 φ(n)

歐拉函數計算機 φ(n)

熱門 AI Skill PRO

輸入計算

數學公式

φ(n)=n∏p|n(1−1p)\varphi\!\left(\text{n}\right) = \text{n} \prod_{p \mid \text{n}} \left(1 - \frac{1}{p}\right)
使用統計

廣告

結果

歐拉函數 φ(15)
8
與此數互質的整數 15 in [1, n]
輸入 n 15
相異質因數 3, 5

回報本頁錯誤

什麼是歐拉函數?

歐拉函數記作 \(\varphi(n)\),用來計算在 1 到 n 之間,有多少個正整數和 n 的最大公因數為 1,也就是與 n 互質的整數個數。舉例來說,\(\varphi(9) = 6\),因為 1、2、4、5、7、8 這六個數都與 9 互質。歐拉函數是數論中的核心概念,也廣泛應用於密碼學領域;其中最著名的就是 RSA 演算法——\(\varphi(n)\) 決定了產生金鑰時所需的模反元素。

1 到 12 的整數網格,標示與 12 互質的數
歐拉函數統計 n 以內與 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 分解為質因數,再乘以 (1 減 1 除以 p) 各項
乘積公式將 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\)。

  1. 從 \(210\) 開始。
  2. 乘以 \(1-\frac{1}{2} = \frac{1}{2}\):\(210 \cdot \frac{1}{2} = 105\)。
  3. 乘以 \(1-\frac{1}{3} = \frac{2}{3}\):\(105 \cdot \frac{2}{3} = 70\)。
  4. 乘以 \(1-\frac{1}{5} = \frac{4}{5}\):\(70 \cdot \frac{4}{5} = 56\)。
  5. 乘以 \(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)\);這正是為什麼可以用相異質數的乘積來計算的原因。

最後更新:

數學和統計熱門計算器

查看全部數學和統計計算器