欧拉函数 φ(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)
使用统计

广告

结果

欧拉函数 φ(210)
48
与此数互质的整数 210 in [1, n]
输入 n 210
不同的质因数 2, 3, 5, 7

报告本页错误

什么是欧拉函数?

欧拉函数记作 \(\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)\)。这正是为什么对不同质数取乘积的公式能够成立的原因。

最后更新:

数学和统计热门计算器

查看全部数学和统计计算器