φ(n)
素因数
互素比例
因数个数

          显示

          进一步了解欧拉函数

          欧拉函数计算器

          在 1 到 12 中,只有 1、5、7 和 11 与 12 没有公因数,所以 φ(12) = 4。欧拉函数对任意 n 统计这样的互素的数。输入一个不超过 10^18 的数,即可得到 φ(n) 以及它的素因数和写出的乘积公式,看到 1 到 n 中与 n 互素的数被突出显示,验证欧拉定理,一次绘制多达 100,000 个数的 φ(k),或者找出所有具有给定 φ(n) 的 n。 输入一个不超过 10^18 的整数 n,或选择一个例题。方块显示 φ(n)、n 的素因数、1 到 n 中与 n 互素的数所占的比例以及因数的个数,步骤用你的数字写出乘积公式。n 不超过 500 时会画出 1 到 n:与 n 互素的数是实心的,其余的数用它们与 n 共有的最小素数的颜色表示。指向一个数可以看到它与 n 的 gcd,点击它则把它用作欧拉定理中的 a。“图表”显示直到某个上限的每个 k 的 φ(k);点击一个点即可打开该数。“反求”列出所有满足 φ(n) = m 的 n;点击其中一个即可打开。

          它是如何运作的

          1. 输入一个不超过 10^18 的整数 n,或选择 φ(60)、RSA 模数或卡迈克尔数 561 等例题。
          2. 读出 φ(n)、素因数和用你的数字写出的乘积公式。不超过 500 时,指向 1 到 n 中的数可看到它与 n 的 gcd,点击其中一个即可用它验证欧拉定理。
          3. 切换到“图表”查看 100,000 以内每个 k 的 φ(k),或切换到“反求”列出所有满足 φ(n) = m 的 n。

          φ(n) 怎样计算

          把 n 分解成素因数,并对每个整除 n 的素数 p,把 n 乘以 (1 − 1/p)。对于 60 = 2² × 3 × 5,得到 60 × 1/2 × 2/3 × 4/5 = 16。划去法得到同样的个数:60 个数中有 30 个是偶数;30 个奇数中有 10 个是 3 的倍数;剩下的 20 个中有 4 个是 5 的倍数,最后剩下 16 个。对素数的幂,公式是 φ(p^k) = p^(k−1)(p − 1),各个值相乘:φ(60) = 2 × 2 × 4。难点在于分解。计算器使用试除法、米勒-拉宾素性检验和波拉德 rho 算法,因此即使是两个 9 位素数相乘得到的 18 位数,也只需不到一秒。

          欧拉函数用在哪里

          φ(n) 统计 0 到 1 之间已经是最简分数的 k/n 的个数,统计能让指针走遍 n 小时钟面上每一个小时的步长(12 小时钟面上是 1、5、7 和 11),也统计模 n 有逆元的数。欧拉证明了对每个与 n 互素的 a 都有 a^φ(n) ≡ 1 (mod n),RSA 加密正是建立在这一点上:取 n = 3233 = 61 × 53,φ(n) = 60 × 52 = 3,120,公开指数 17 的私钥伙伴是 2,753,因为 17 × 2,753 = 15 × 3,120 + 1。

          常见问题

          什么是欧拉函数?

          φ(n) 是 1 到 n 中除 1 以外与 n 没有公因数的整数的个数。φ(9) = 6,因为 1、2、4、5、7 和 8 与 9 互素,而 3、6 和 9 都含有因数 3。按照约定,φ(1) = 1。欧拉在 18 世纪 60 年代研究了这个函数;高斯在 1801 年给它取了符号 φ,詹姆斯·约瑟夫·西尔维斯特在 1879 年给了它英文名称 totient。

          素数的 φ 值是多少?

          是 p − 1,因为 1 到 p − 1 中的每个数都与素数 p 互素,所以 φ(97) = 96。对于素数的幂,φ(p^k) = p^k − p^(k−1),因为只有 p 的倍数与它有公因数:φ(81) = 81 − 27 = 54。

          欧拉定理说的是什么?

          如果 a 与 n 互素,那么 a^φ(n) 除以 n 的余数是 1。取 n = 60、a = 7:φ(60) = 16,且 7^16 ≡ 1 (mod 60)。费马小定理就是 n 为素数的情形。往往更小的指数就已经成立:7^4 = 2,401 = 40 × 60 + 1。对所有与 n 互素的 a 都成立的最小指数是卡迈克尔函数 λ(n),对 60 来说是 4。

          两个数的欧拉函数值可以相同吗?

          可以,而且通常有好几个:n = 35、39、45、52、56、70、72、78、84 和 90 时都有 φ(n) = 24。有些偶数永远不是 φ 的值,其中最小的是 14;大于 1 的奇数也都不是,因为从 n = 3 起 φ(n) 都是偶数。罗伯特·卡迈克尔在 1907 年断言,没有哪个值恰好只出现一次。这至今仍未被证明,凯文·福特在 1998 年证明,如果存在例外,它必须大于 10^(10^10)。

          可以输入多大的数?

          任何不超过 10^18 的整数。计算器在你的浏览器中用精确的整数运算来分解它,因此 φ(10^18) = 4 × 10^17 和 φ(999,999,866,000,004,473) = 999,999,864,000,004,608 都精确到最后一位。1 到 n 的数在 n 不超过 500 时画出,图表最多到 100,000,反求适用于不超过 10^10 的值。

          准备好尝试了吗?

          在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

          前往编辑器