欧拉函数计算器

计算正整数n的欧拉函数φ(n)并展示互质数

输入正整数
请输入大于0的整数
10 15 21 30 100 2310
欧拉函数结果

4

对于 n = 10

使用说明
  • 输入一个正整数（n ≥ 1）
  • 计算欧拉函数φ(n)的值
  • 查看质因数分解过程
  • 列出所有与n互质的数
  • 了解欧拉函数的性质和应用
欧拉函数结果

4

对于 n = 10

质因数分解
10 = 2 × 5
质因数分解详情
质因数 指数 贡献因子
2 1 (1 - 1/2)
5 1 (1 - 1/5)
互质数列表

小于 10 且与 10 互质的正整数：

1 3 7 9

总计：4 个互质数

互质数验证
数字 与n的GCD 是否互质
1 1 是
2 2 否
3 1 是
4 2 否
5 5 否
6 2 否
7 1 是
8 2 否
9 1 是
计算步骤
欧拉函数计算步骤：
1
质因数分解：
\[ n = 10 = 2^1 \times 5^1 \]
2
应用欧拉函数公式：
\[ \phi(n) = n \times \prod_{p|n} \left(1 - \frac{1}{p}\right) \]

其中 p 是 n 的质因数

3
代入质因数：
\[ \phi(10) = 10 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{5}\right) \]
4
计算各部分：
\[ 1 - \frac{1}{2} = \frac{1}{2} \] \[ 1 - \frac{1}{5} = \frac{4}{5} \]
5
计算结果：
\[ \phi(10) = 10 \times \frac{1}{2} \times \frac{4}{5} = 10 \times \frac{4}{10} = 4 \]
6
验证互质数：

小于10且与10互质的数：1, 3, 7, 9

总计4个，与计算结果一致

欧拉函数：概念与应用

什么是欧拉函数？

欧拉函数φ(n)（也称为欧拉总计函数）是数论中的一个重要函数，表示小于或等于n的正整数中与n互质的数的个数。 其中，互质是指两个数的最大公约数（GCD）为1。

数学表达

欧拉函数的计算公式为：

\[ \phi(n) = n \times \prod_{p|n} \left(1 - \frac{1}{p}\right) \]

其中 p 是 n 的所有不同的质因数。

欧拉函数的性质
性质 描述 示例
质数 若p是质数，则φ(p) = p-1 φ(7) = 6
质数幂 若p是质数，则φ(pᵏ) = pᵏ - pᵏ⁻¹ φ(8) = φ(2³) = 8 - 4 = 4
乘法性 若m,n互质，则φ(mn) = φ(m)φ(n) φ(15) = φ(3)φ(5) = 2×4 = 8
偶数 若n>2，则φ(n)总是偶数 φ(10)=4, φ(15)=8
欧拉定理 若a,n互质，则aᵠ⁽ⁿ⁾ ≡ 1 (mod n) 3⁴ ≡ 1 (mod 10)
应用场景
1 RSA加密算法
2 模运算与同余方程
3 数论证明与定理
4 密码学与信息安全
5 群论与抽象代数
6 组合数学与计数问题
RSA加密中的应用

RSA加密算法是欧拉函数最重要的应用之一：

  1. 选择两个大质数 p 和 q
  2. 计算 n = p × q
  3. 计算 φ(n) = (p-1)(q-1)
  4. 选择加密指数 e，使得 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
  5. 计算解密指数 d，使得 d × e ≡ 1 (mod φ(n))
  6. 公钥为 (n, e)，私钥为 (n, d)

欧拉定理保证了加密和解密过程的正确性：

\[ m^{ed} \equiv m \pmod{n} \]

相关概念
最大公约数 (GCD)

两个或多个整数的最大公约数

gcd(a,b) = 最大整数d使得d|a且d|b

最小公倍数 (LCM)

两个或多个整数的最小公倍数

lcm(a,b) = |a×b| / gcd(a,b)

欧拉定理

若a,n互质，则

\[ a^{\phi(n)} \equiv 1 \pmod{n} \]

互质数示例
n = 15

互质数：1, 2, 4, 7, 8, 11, 13, 14

φ(15) = 8

n = 21

互质数：1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20

φ(21) = 12

欢迎使用我们的专业在线欧拉函数计算器！这是一个为数学爱好者、学生、教师以及密码学研究者打造的免费工具，旨在帮助您省去繁琐的手动计算，瞬间获得任意正整数 n的欧拉函数值 φ(n)。什么是欧拉函数？欧拉函数，通常记作 φ(n)，是数论中一个非常重要的函数。它表示的是在小于等于正整数 n的所有正整数中，与 n互质（即最大公约数为1）的数的个数。例如，φ(9) = 6，因为在1到9之间，与9互质的数有1, 2, 4, 5, 7, 8，共计6个。欧拉函数在密码学（尤其是RSA加密算法）、群论等领域有着基础而广泛的应用。如何使用本计算器？我们的工具设计极其简单，完全符合您的使用习惯：
  1. 输入数值：在指定的输入框中，键入您想要计算的正整数 n。
  2. 点击计算：按下“计算”按钮。
  3. 获取结果：系统将立即在结果区域显示 φ(n)的值。
整个过程无需注册、无需安装插件，完全在浏览器中安全运行。工具核心功能与优势
  • 极速计算：依托高效算法，无论 n多大，都能在毫秒级时间内返回准确的 φ(n)值。
  • 结果精准：确保计算结果的数学严谨性，为您的学术研究或作业提供可靠依据。
  • 完全免费：本工具完全免费使用，无任何隐藏费用或次数限制。
  • 跨平台兼容：无论是在Windows、macOS电脑上，还是在使用iOS或安卓系统的手机和平板上，都能通过浏览器流畅访问。
  • 用户友好：界面简洁直观，操作逻辑清晰，即使是初次接触欧拉函数的用户也能轻松上手。
欧拉函数的应用场景
  • 密码学：RSA公钥加密算法的安全性核心之一便是基于欧拉定理，该定理涉及欧拉函数的计算。理解 φ(n)对于学习现代密码学至关重要。
  • 数学学习：对于学习初等数论、抽象代数的学生来说，本工具是验证手算结果、探索函数性质的绝佳伴侣。
  • 问题研究：当需要快速验证多个大数的欧拉函数值以寻找规律或解决特定数学问题时，本工具能极大提升您的研究效率。
常见问题（FAQ）
  • Q：这个计算器能处理的最大数值是多少？
    • A：理论上可以处理非常大的数字，但受限于JavaScript引擎的数值精度，对于极大的数字（如超过20位的整数），可能会存在精度限制。对于常规数学学习和研究，完全足够。
  • Q：计算器会显示计算步骤吗？
    • A：是的，对于有教学意义的数字，我们会尝试展示简要的质因数分解过程，帮助您理解 φ(n)是如何得出的。
  • Q：欧拉函数和质数有什么关系？
    • A：如果一个数 p是质数，那么所有小于它的正整数都与它互质，因此 φ(p) = p - 1。这是欧拉函数的一个基本性质。
立即尝试输入一个数字，体验高效计算的便捷吧！如果您觉得这个工具对您有帮助，欢迎收藏本页或分享给您的同学和同事。

相关工具