Euler's Totient Function φ(n): Counting Primes & Residue Systems

需积分: 10 51 浏览量更新于2024-09-06 收藏 200KB PDF 举报

Euler totient函数φ(n)，在数学中被简称为欧拉函数，是一个重要的数论概念，其定义在OEIS（Online Encyclopedia of Integer Sequences）中的编号为A000010。这个函数的基本任务是计算不大于n的所有整数中，与n互质（即除1和n本身外没有其他公因数）的数目。换句话说，φ(n)给出了在模n下，所有单位元（即逆元）的集合大小，它们在环Z/nZ中的数量。 φ(n)与许多数学对象密切相关： 1. 剩余类系统：它表示的是模n的剩余类的个数，这些类中每个元素都是与n互质的。 2. 循环多项式：φ(n)也是n-th阶循环多项式的次数，这是指次数最小的多项式，其根包含所有n的原始根，即满足x^n-1=0且x不是n的幂次的复数根。 3. 群论中的生成元：φ(n)给出了一个阶为n的循环群（群中元素的乘积形成一个循环）的唯一生成元的数量。原始n-th根相当于该群的一个生成元。 4. 狄利克雷字符：在数论中的复分析中，φ(n)也对应着模n的复数狄利克雷字符的数量。这些字符是复函数，它们在处理模形式和L-函数时扮演关键角色。 5. 渐近行为：有趣的是，当n趋向无穷大时，φ(n)的增长速度与π²有密切关系。具体来说，对于足够大的n，φ(n)的值大致上等于(3/π²) * n²，这反映了素数分布对欧拉函数的影响。 Euler totient函数φ(n)在密码学、数论和组合数学中有广泛应用，特别是在RSA公钥加密算法中，它用于确定密钥参数的选择。理解并计算φ(n)对于许多理论问题和实际问题解决都至关重要，比如确定一个数是否为质数或者寻找特定类型的数论结构。因此，掌握欧拉函数及其性质对于研究者和实践者来说都是非常基础且实用的知识。

展开

10/8/2018 A000010 - OEIS
https://oeis.org/A000010 1/5
log in
This site is supported by donations to The OEIS Foundation. 
 
 
The October issue of the Notices of the Amer. Math. S oc. has an article about the OEIS. 
 
Search
Hints
(Greeting s from The On-Line Encyclopedia of Integ er Sequences!)
A000010 Euler totient function phi(n): count numbers <= n and prime to n. 
(Formerly M0299 N0111)
2600
1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12,
18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16,
42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44 (list;
g raph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
Number of elements in a reduced residue system modulo n.
Degree of the n-th cyclotomic polynomial (cf. A013595). - Benoit Cloitre,
Oct 12 2002
Number of distinct generators of a cyclic group of order n. Number of
primitive n-th roots of unity. (A primitive n-th root x is such that x^k
is not equal to 1 for k = 1, 2, ..., n - 1, but x^n = 1.) - Lekraj
Beedassy, Mar 31 2005
Also number of complex Dirichlet characters modulo n; sum(k = 1, n, a(k))
is asymptotic to (3/Pi^2)*n^2. - Steven Finch, Feb 16 2006
a(n) is the highest degree of irreducible polynomial dividing 1 + x + x^2 +
... + x^(n-1) = (x^n - 1)/(x - 1). - Alexander Adamchuk, Sep 02 2006,
corrected Sep 27 2006
a(p) = p - 1 for prime p. a(n) is even for n > 2. For n > 2 a(n)/2 =
A023022(n) = number of partitions of n into 2 ordered relatively prime
parts. - Alexander Adamchuk, Jan 25 2007
Number of automorphisms of the cyclic group of order n. - Benoit Jubin, Aug
09 2008
a(n+2) equals the number of palindromic Sturmian words of length n which
are 'bispecial', prefix or suffix of two Sturmian words of length n + 1.
- Fred Lunnon, Sep 05 2010
Suppose that a and n are coprime positive integers, then by Euler's totient
theorem, any factor of n divides a^phi(n) - 1. - Lei Zhou, Feb 28 2012
a(n) = A096396(n) + A096397(n). - Reinhard Zumkeller, Mar 24 2012
If m has k prime factors,(f1, f2, ..., fk), then phi(m*n) = phi(f1*n) *
phi(f2*n) * ... * phi(fk*n)/phi(n)^(k-1). For example, phi(42*n) =
phi(2*n) * phi(3*n) * phi(7*n)/phi(n)^2. - Gary Detlefs, Apr 21 2012
Sum(n>=1, a(n)/n! ) = 1.954085357876006213144... This sum is referenced in
Plouffe's inverter. - Alexander R. Povolotsky, Feb 02 2013
The order of the multiplicative group of units modulo n. - Michael Somos,
Aug 27 2013
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for
all positive integers n and m. - Michael Somos, Dec 30 2016
From Eric Desbiaux, Jan 01 2017: (Start)
a(n) equals the Ramanujan sum c_n(n) (last term on n-th row of triangle
A054533).
a(n) equals the Jordan function J_1(n) (cf. A007434, A059376, A059377,
which are the Jordan functions J_2, J_3, J_4, respectively). (End)