# 欧拉函数 φ(n) 计算器

计算欧拉函数 φ(n)——[1, n] 中与 n 互素的正整数个数。先做试除法质因数分解，再按 φ(n) = n · Π(1 − 1/p) 精确求值（n ≤ 10¹²），可附带列出前 60 个互素数，并给出欧拉定理 a^φ(n) ≡ 1 (mod n)。经典例：φ(36) = 12（36 = 2² × 3²）；n 为素数时 φ(n) = n − 1，如 φ(97) = 96。

> 标准页面: https://elysiatools.com/zh/tools/euler-totient-function

- **分类:** Math & Numbers

- **关键词:** 欧拉函数, 互素, 质因数分解, 欧拉定理, 数论, 积性函数

## 概述

欧拉函数 φ(n) 计算器用于计算区间 [1, n] 内与正整数 n 互素的整数个数。工具通过试除法对输入的正整数（支持 n ≤ 10¹²）进行质因数分解，并利用公式 φ(n) = n · Π(1 − 1/p) 精确求解，同时支持列出前 60 个互素数并展示对应的欧拉定理公式。

## 输入项

- **数字 n** (text): Positive integer, 1 ≤ n ≤ 10¹² (trial-division factorization bound).
- **输出详细度** (select)

## 适用场景

- 在数论或离散数学学习中需要快速验证正整数的质因数分解及欧拉函数计算结果时。
- 设计或分析 RSA 等基于模运算的公钥密码学算法时，需要求解模数 φ(n) 以生成私钥指数。
- 求解模同余方程并需要利用欧拉定理 a^φ(n) ≡ 1 (mod n) 进行模幂降幂化简时。

## 工作原理

- 输入 1 到 10¹² 之间的正整数 n，并选择详细度模式（仅输出计算值或同时列出互素数）。
- 工具采用试除法对 n 进行完全质因数分解，提取所有不重复的质因子 p。
- 根据欧拉乘积公式 φ(n) = n · Π(1 − 1/p) 展开并精确计算互素正整数的总数。
- 输出质因数分解式、φ(n) 计算步骤及欧拉定理公式；若开启列表模式，还会显示前 60 个与 n 互素的具体数值。

## 使用案例

- 数论教学与作业验证：学生与教师用于核对合数质因数分解及欧拉函数手算结果。
- 现代密码学密钥计算：计算两素数乘积模数 n = p · q 的 φ(n) = (p - 1)(q - 1)，辅助理解 RSA 密钥生成机制。
- 同余方程化简：在竞赛编程或数学计算中，利用求得的 φ(n) 对大数模幂指数取模降幂。

## 常见问题

### 欧拉函数 φ(n) 的数学定义是什么？

欧拉函数 φ(n) 表示小于或等于正整数 n 的正整数中，与 n 互素（即最大公约数 gcd(a, n) = 1）的元素个数。

### 如果输入的数字 n 是质数，φ(n) 等于多少？

当 n 为质数时，1 到 n - 1 的所有整数都与 n 互素，因此 φ(n) = n - 1。

### 计算器支持输入的最大数值是多少？

工具基于试除法质因数分解实现，支持的最大正整数为 10¹²（1,000,000,000,000）。

### 互素数列表最多可以显示多少个？

当输出详细度选择“同时列出互素数”时，工具最多显示前 60 个与 n 互素的正整数。

### 输出中的欧拉定理有什么作用？

欧拉定理表明若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)，常用于模幂运算的指数化简和密码学密钥推导。

## 相关工具

- [Carmichael 函数 λ(n) 计算器](https://elysiatools.com/zh/tools/carmichael-function): 计算 Carmichael 函数 λ(n)——乘法群 (Z/nZ)* 的指数，即使所有与 n 互素的 a 满足 a^k ≡ 1 (mod n) 的最小 k。由质因数分解按 λ(2)=1、λ(4)=2、λ(2^k)=2^(k−2)（k ≥ 3）、奇素数幂 λ(p^k)=φ(p^k) 再取 lcm 得到，同时给出 φ(n) 对比、是否存在原根，并用 Korselt 判据识别 Carmichael 数。经典例：λ(561) = 80（561 是最小的 Carmichael 数），而 λ(8) = 2 < φ(8) = 4。
- [中国剩余定理求解器（同余方程组）](https://elysiatools.com/zh/tools/chinese-remainder-theorem): 求解同余方程组 x ≡ rᵢ (mod mᵢ)（2–20 条方程），采用逐对合并的广义中国剩余定理：模数两两互素时合并模数为乘积，非互素但相容时合并模数为最小公倍数，不相容（公因数不整除余数差）则明确报告无解。每条方程都会对最终解回代验证。经典例：x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7) 的解为 x = 23 (mod 105)。
- [排列 / 组合 / 子集生成器（支持重复元素）](https://elysiatools.com/zh/tools/combinatorial-generation): 生成多重集的排列、组合与子集，自动去重并按字典序输出：排列用 next_permutation，精确计数 n!/Π(mᵢ!)；组合生成不同的 k-子多重集，计数为 Π(1+x+…+x^mᵢ) 中 x^k 的系数（元素互异时即 C(n,k)）；子集枚举所有子多重集，计数 Π(mᵢ+1)（互异时 2ⁿ），含空集。最多 12 个元素，展示上限 200 条但计数始终精确；组合模式要求 1 ≤ k ≤ n。经典例：\[A, A, B\] 的排列 → 3!/2! = 3 个（AAB、ABA、BAA）；\[A, A, B\] 的子集 → (2+1)(1+1) = 6 个。
- [零和博弈求解器（鞍点 / 线性规划混合策略）](https://elysiatools.com/zh/tools/game-theory-zero-sum): 求解 2–6 × 2–6 双人零和博弈（支付矩阵归行方——最大化者，列方支付）：先做鞍点检验（行最小值的最大值 = 列最大值的最小值时存在纯策略均衡，列出所有鞍点格）；否则移位矩阵使元素 ≥ 1 后用单阶段单纯形（松弛基、Bland 规则）求解 max Σz s.t. Bz ≤ 1，其原始解给出列方混合策略 q，对偶影子价格恰为行方 LP 解 y，值移回后给出 x、q、v，并数值验证双方安全策略（xᵀA ≥ v、Aq ≤ v）与极小极大相等。经典例：猜硬币 \[\[1,-1\],\[-1,1\]\] → 值 0，双方各以 0.5/0.5 混合。
- [拉普拉斯逆变换计算器（部分分式法）](https://elysiatools.com/zh/tools/inverse-laplace-calculator): 对有理函数 F(s) = N(s)/D(s)（真分式，分母次数 ≤ 6）求拉普拉斯逆变换：先对分母求根并按重数/共轭对分组，再解多项式系数线性方程组得到部分分式分解，最后逐项查表反变换（A/(s−r)→Ae^(rt)、A/(s−r)^j→At^(j−1)e^(rt)/(j−1)!、(Bs+C)/((s−α)²+β²)→e^(αt)\[Bcos(βt)+…sin(βt)\]）。经典例：1/(s²+3s+2) → e^(−t)−e^(−2t)；(3s+5)/(s²+4) → 3cos(2t)+2.5sin(2t)。
- [拉普拉斯变换计算器（常用函数对查表）](https://elysiatools.com/zh/tools/laplace-transform-calculator): 查表求常用函数的拉普拉斯变换 F(s) = ∫₀^∞ e^(−st)f(t)dt：覆盖 14 组标准变换对（1、t、tⁿ、e^(at)、tⁿe^(at)、sin/cos(kt) 及其指数移位、sinh/cosh、t·sin/t·cos、δ(t)），带参数代入、收敛域（如 s > a）、推导要点，并可在指定 s 处数值求值（自动校验收敛）。示例：L{e^t} = 1/(s−1)，s>1，F(2) = 1。
- [模 n 乘法阶计算器（乘法群元素阶）](https://elysiatools.com/zh/tools/order-of-element-mod-n): 求元素 a 模 n 的乘法阶 ord\_n(a)——使 a^k ≡ 1 (mod n) 的最小 k ≥ 1（要求 gcd(a, n) = 1）。算法从 φ(n) 出发逐个剥去素因子并测试 a^(ord/p)，输出 a 的幂表、最小性证明（对每个整除 k 的素数 p 验证 a^(k/p) ≢ 1）、生成的循环子群 ，并标注 a 是否为原根（ord = φ(n)）或达到最大阶（ord = λ(n)）。经典例：ord\_7(3) = 6 = φ(7)，3 是 mod 7 的原根；ord\_15(2) = 4 < φ(15) = 8。
- [部分分式分解计算器（有理函数）](https://elysiatools.com/zh/tools/partial-fraction-decomposer): 对有理函数 F(x) = N(x)/D(x) 做部分分式分解（分母次数 ≤ 6，分子次数 ≤ 8，假分式自动先做多项式长除）：Durand-Kerner 求分母根并按重数/共轭对分组，解多项式系数线性方程组得到 A/(x−r)^j 与 (Bx+C)/((x−α)²+β²) 形式的分解，并在代数探针点做数值残差验证。经典例：(3x+5)/(x²+3x+2) = 2/(x+1) + 1/(x+2)；(x³+2x)/(x²+1) = x + x/(x²+1)；1/(x(x+1)²) = 1/x − 1/(x+1) − 1/(x+1)²。

## 示例

- [Web Python 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-python): Web Python 图像处理示例，使用 PIL/Pillow 包括读取、保存、缩放和格式转换
- [Android Java 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-java): Android Java 图像处理示例，包括图像读取保存、缩放和格式转换
- [Android Kotlin 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-kotlin): Android Kotlin 图像处理示例，包括图像读取保存、缩放和格式转换
- [Web Rust 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-rust): Web Rust 图像处理示例，包括图像读取保存、缩放和格式转换