Euler's totient function
Euler's totient function, commonly denoted as φ(n), is an arithmetic function that counts the positive integers up to a given positive integer n which are relatively prime to n.[1] This count includes 1 and excludes any multiples of the prime factors of n, making φ(n) a measure of the "density" of integers coprime to n in the range from 1 to n.[2] The explicit formula for φ(n) is φ(n) = n ∏_{p | n} (1 - 1/p), where the product runs over the distinct prime factors p of n.[1] For a prime power p^k, φ(p^k) = p^k - p^{k-1}, and the function is multiplicative: if m and n are coprime, then φ(mn) = φ(m) φ(n).[2] A key property is that the sum of φ(d) over all positive divisors d of n equals n, i.e., ∑_{d | n} φ(d) = n.[1] Additionally, φ(n) is even for all n ≥ 3, and it satisfies inequalities such as φ(n) > c n / \log \log n for some constant c and sufficiently large n.[1] Leonhard Euler first introduced the totient function in 1763 in his paper "Demonstration of a new method in the theory of arithmetic" (E271), where he used it to prove a generalization of Fermat's Little Theorem known as Euler's theorem: if a and n are coprime, then a^{φ(n)} ≡ 1 \pmod{n}.[3] The modern notation φ(n) was adopted by Carl Friedrich Gauss in 1801 in his Disquisitiones Arithmeticae, while the term "totient" was coined by J. J. Sylvester in 1879.[3] The function plays a central role in analytic number theory, appearing in the Dirichlet series ∑ φ(n)/n^s = ζ(s-1)/ζ(s) for Re(s) > 2, where ζ(s) is the Riemann zeta function.[1] Beyond pure mathematics, Euler's totient function is essential in cryptography, particularly in the RSA algorithm, where φ(n) for a semiprime n = pq (with p and q distinct primes) determines the exponent for modular exponentiation to ensure secure key generation and encryption.[4] It also underlies pseudorandom number generation and primality testing in computational number theory.[1]Definition, History, and Notation
Definition
Euler's totient function, denoted \phi(n), counts the number of positive integers k such that $1 \leq k \leq n and k is coprime to n, formally defined as \phi(n) = \left| \{ k : 1 \leq k \leq n, \gcd(k,n)=1 \} \right|. [1] Two positive integers are coprime if their greatest common divisor is 1, meaning they share no prime factors in common. For example, with n=6, the integers from 1 to 6 are checked for coprimality: only 1 and 5 satisfy \gcd(k,6)=1, so \phi(6)=2.[1] This counting of coprimes to n relies on the inclusion-exclusion principle, which systematically subtracts and adds back multiples of the prime factors of n to determine the size of the set of integers up to n avoiding those factors.[5] By convention, \phi(1)=1, as the single integer 1 is coprime to itself.[1] The function is named after the mathematician Leonhard Euler, who introduced it in his 1763 paper Theoremata arithmetica nova methodo demonstrata.[6]Historical Development
Leonhard Euler introduced the totient function in his 1763 paper "Theoremata arithmetica nova methodo demonstrata" (E271), where he defined it as the number of positive integers up to n that are relatively prime to n. Euler provided initial computations for small values and established key properties, including the formula for prime powers \phi(p^m) = p^{m-1}(p-1) and the multiplicative property \phi(ab) = \phi(a)\phi(b) when a and b are coprime, laying the groundwork for its product formula \phi(n) = n \prod_{p \mid n} (1 - 1/p) developed around the same period. These contributions appeared in the context of his broader investigations into arithmetic progressions and divisor counts.[7] In 1801, Carl Friedrich Gauss referenced Euler's function in his seminal work Disquisitiones Arithmeticae, introducing the notation \phi(n) and crediting Euler while expanding on its properties, such as the sum-of-divisors identity \sum_{d \mid n} \phi(d) = n. Gauss's adoption and notation helped standardize the function within number theory, emphasizing its role in understanding the structure of integers and residues modulo n. This publication marked a pivotal milestone, integrating the totient into systematic treatments of congruences and primitive roots.[8] The term "totient" was coined in 1879 by James Joseph Sylvester in his paper "On certain ternary cubic-form equations," where he formalized the function's study in the context of ternary cubic forms and proposed alternative notations like \tau(n), though \phi(n) prevailed. Later in the 19th century, Camille Jordan generalized the totient to higher powers with Jordan's totient function J_k(n) = n^k \prod_{p \mid n} (1 - 1/p^k) for k \geq 1, extending its applications to counting k-tuples coprime to n. By the late 19th and early 20th centuries, the totient function evolved into a cornerstone of modern number theory, influencing Dirichlet's proofs on primes in arithmetic progressions (1837) through its appearance in L-functions and density estimates, and later in analytic number theory via works on the Riemann zeta function and distribution of primes. Its multiplicative nature and connections to group orders in modular arithmetic facilitated advancements in algebraic number theory and cryptography in the 20th century.Notation and Terminology
The standard notation for Euler's totient function is \phi(n), where n is a positive integer, introduced by Carl Friedrich Gauss in his 1801 work Disquisitiones Arithmeticae to denote the count of integers up to n that are relatively prime to n. Earlier, Leonhard Euler described the concept without a dedicated symbol in his 1758 paper, referring to it descriptively as the "multitude of numbers less than N prime to N", and later employed \pi N in a 1775 publication to represent the same quantity. A variant form, \varphi(n) or \phi(n) with the variant Greek phi, is also commonly used interchangeably in modern texts, while informal abbreviations like \mathrm{tot}(n) occasionally appear in computational contexts.[9] The term "totient" itself was coined in 1879 by James Joseph Sylvester, who proposed the symbol \tau(n) but favored the name derived from the Latin totiens ("so many times"), evoking a sense of quantity akin to "quotient". Despite this, the function is most widely known as "Euler's totient function" in recognition of Euler's foundational contributions. To distinguish it from related concepts, Euler's totient function \phi(n) specifically counts coprime residues modulo n, whereas Jordan's totient functions J_k(n) for k > 1, introduced by Camille Jordan, generalize this to count k-tuples of integers up to n that are coprime to n in a componentwise manner, with J_1(n) = \phi(n).Computation
Multiplicative Property
One of the fundamental properties of Euler's totient function \phi is its multiplicativity. Specifically, if m and n are positive integers such that \gcd(m, n) = 1, then \phi(mn) = \phi(m) \phi(n).[10] This property arises because the integers between 1 and mn that are coprime to mn are exactly those coprime to both m and n, allowing the count of such integers to factor naturally under coprimality.[11] A standard proof of this multiplicativity relies on the Chinese Remainder Theorem. When \gcd(m, n) = 1, the theorem provides a ring isomorphism \mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}. This isomorphism restricts to a bijection between the multiplicative groups of units (\mathbb{Z}/mn\mathbb{Z})^\times and (\mathbb{Z}/m\mathbb{Z})^\times \times (\mathbb{Z}/n\mathbb{Z})^\times, since an element is invertible modulo mn if and only if it is invertible modulo both m and n. The orders of these groups are \phi(mn), \phi(m), and \phi(n), respectively, so the bijection implies \phi(mn) = \phi(m) \phi(n).[10] As a consequence, the value of \phi(n) for any positive integer n > 1 is fully determined by the prime factorization of n, since n can be uniquely decomposed into coprime prime power factors and \phi multiplies over them.[11]Product Formula
The explicit product formula for Euler's totient function \phi(n) expresses it in terms of the distinct prime factors of n. Suppose n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}, where the p_i are distinct primes and each k_i \geq 1. Then, \phi(n) = n \prod_{i=1}^r \left(1 - \frac{1}{p_i}\right). This closed-form expression was introduced by Leonhard Euler in his 1763 paper on arithmetic theory.[12] It provides a direct computational tool based on the prime factorization of n, leveraging the fundamental theorem of arithmetic for its general applicability.[3] The formula derives from the known values of \phi at prime powers, combined with the multiplicative property of the function. For a prime power p^k, the totient is \phi(p^k) = p^k - p^{k-1} = p^k \left(1 - \frac{1}{p}\right), which counts the integers from 1 to p^k that are not multiples of p.[12] Since \phi is multiplicative—meaning \phi(mn) = \phi(m) \phi(n) when \gcd(m,n) = 1—it follows that \phi(n) = \prod_{i=1}^r \phi(p_i^{k_i}) for the prime factorization of n. Substituting the prime power expression yields the product formula.[3] The term \left(1 - \frac{1}{p_i}\right) in the product arises from the inclusion-exclusion principle applied to the definition of \phi(n), which counts integers up to n coprime to n by excluding those sharing a prime factor with n. For the full set of distinct primes dividing n, the proportion of such coprime integers is precisely \prod_{p \mid n} \left(1 - \frac{1}{p}\right), as the inclusion-exclusion expansion over the primes p_i simplifies to this product form.[13] This connection underscores the formula's roots in sieve methods for counting residue classes modulo n.[12]Divisor Sum Formula
One alternative expression for Euler's totient function \phi(n) is the divisor sum formula, which involves a summation over the divisors of n weighted by the Möbius function \mu: \phi(n) = \sum_{d \mid n} \mu(d) \frac{n}{d}. This representation, first derived by Mertens in 1874, complements the product formula by providing a direct arithmetic series form.[1][14] The derivation proceeds via Möbius inversion applied to the known identity \sum_{d \mid n} \phi(d) = n, which counts the total number of integers from 1 to n partitioned by their gcd with n. Here, the left side sums \phi(d) over divisors d of n, where each \phi(d) counts the integers up to n that are multiples of n/d and coprime to n/d. By the Möbius inversion theorem for arithmetic functions, if g(n) = \sum_{d \mid n} f(d) with g(n) = n and f = \phi, then \phi(n) = \sum_{d \mid n} \mu(d) g(n/d) = \sum_{d \mid n} \mu(d) (n/d). This inversion directly yields the formula and establishes its equivalence to the count of integers coprime to n.[15] The appearance of the Möbius function \mu(d) in the sum encodes the inclusion-exclusion corrections for overcounting multiples of prime factors in the coprimality condition. For instance, positive terms (\mu(d) = 1) arise for square-free d with an even number of prime factors, subtracting intersections, while negative terms (\mu(d) = -1) add back triple intersections, and \mu(d) = 0 for non-square-free d eliminates higher powers. This structure mirrors the classical inclusion-exclusion principle but generalizes it via the divisor poset.[14][16] Computationally, the divisor sum formula is advantageous when the prime factorization of n is unknown but the list of divisors can be enumerated efficiently, as it requires only evaluating \mu(d) for each d \mid n (by checking square-freeness and parity of distinct primes) rather than identifying the primes explicitly. For example, for n = 30, the divisors are 1, 2, 3, 5, 6, 10, 15, 30; computing \mu(1) = 1, \mu(2) = -1, \mu(3) = -1, \mu(5) = -1, \mu(6) = 1, \mu(10) = 1, \mu(15) = 1, \mu(30) = -1 yields \phi(30) = 30(1 - 1/2 - 1/3 - 1/5 + 1/6 + 1/10 + 1/15 - 1/30) = 8, verifiable against the product formula. This approach proves useful in scenarios like sieve methods or when n has many small divisors.[1]Other Methods
One specialized computational technique for expressing Euler's totient function \phi(n) leverages Fourier analysis on the cyclic group \mathbb{Z}/n\mathbb{Z}, particularly through transforms involving the greatest common divisor function and Ramanujan sums. The Ramanujan sum c_n(m) is defined as c_n(m) = \sum_{\substack{1 \leq k \leq n \\ \gcd(k,n)=1}} \exp\left(2\pi i \frac{km}{n}\right), and notably, c_n(0) = \phi(n), providing a direct link to the totient via this Fourier-like sum over primitive roots of unity. A key formula arises from the Fourier transform of the gcd-dependent function f(k) = \gcd(k,n): \sum_{k=1}^n \gcd(k,n) \exp\left(-2\pi i \frac{k}{n}\right) = \phi(n). This equality follows from the general property that the Fourier transform F_f(m,n) = \sum_{k=1}^n f(\gcd(k,n)) \exp(-2\pi i k m / n) equals the Dirichlet convolution (f * c_{\bullet}(m))(n), where for f the identity function \mathrm{id}(k) = k and m=1, the convolution yields \phi(n) via the relation \phi = \mathrm{id} * \mu and properties of Ramanujan sums.[17] These approaches are applied in analytic number theory, particularly for sieving and probabilistic evaluations of arithmetic sums. For instance, character sums decompose coprimality conditions orthogonally, facilitating estimates in sieving methods like those for the distribution of primes or lattice points free of certain factors, where \phi(n) emerges in densities or error terms. In probabilistic contexts, such expansions aid in analyzing random models over residue classes, such as estimating the probability that two integers are coprime via character averages.[18] For large n, these methods are theoretically elegant but inefficient for direct computation compared to factorization-based techniques. The gcd-exponential sum requires O(n \log n) time to evaluate all terms, while the character sum involves \phi(n) \sim n / \log \log n terms, each needing character evaluation (potentially costly without precomputation). In contrast, the product or divisor sum formulas achieve O(\sqrt{n}) time assuming efficient factorization, though the latter remains the primary bottleneck for unfactored large n without special structure; thus, Fourier/character methods excel in aggregate analytic settings rather than isolated evaluations.[17]Specific Values and Examples
Values for Small Integers
The values of Euler's totient function φ(n) for small positive integers n provide a direct illustration of how many numbers up to n are coprime to n, revealing initial patterns in the distribution of totatives.[1] The following table lists φ(n) for n from 1 to 30, computed as the count of integers k where 1 ≤ k ≤ n and gcd(k, n) = 1; this sequence corresponds to OEIS A000010.[1][9]| n | φ(n) | n | φ(n) | n | φ(n) |
|---|---|---|---|---|---|
| 1 | 1 | 11 | 10 | 21 | 12 |
| 2 | 1 | 12 | 4 | 22 | 10 |
| 3 | 2 | 13 | 12 | 23 | 22 |
| 4 | 2 | 14 | 6 | 24 | 8 |
| 5 | 4 | 15 | 8 | 25 | 20 |
| 6 | 2 | 16 | 8 | 26 | 12 |
| 7 | 6 | 17 | 16 | 27 | 18 |
| 8 | 4 | 18 | 6 | 28 | 12 |
| 9 | 6 | 19 | 18 | 29 | 28 |
| 10 | 4 | 20 | 8 | 30 | 8 |