Euler function
The Euler totient function, commonly denoted \phi(n) or \varphi(n), is an arithmetic function in number theory that counts the number of positive integers up to n which are relatively prime to n.[1][2] This includes 1, which is considered relatively prime to every integer, and excludes multiples of any prime factor of n.[1] For example, \phi(1) = [1](/page/1) and \phi(24) = 8.[1]
Introduced by the Swiss mathematician Leonhard Euler in his 1763 paper "Theoremata ex algebrae speculativae fontibus petita" (E271), the function was originally described without modern notation as the "multitude of numbers less than N prime to N."[3] Euler proved key properties, including the formula for prime powers \phi(p^k) = p^{k-1}(p-1) where p is prime and k \geq 1, and its multiplicativity: if \gcd(a, b) = 1, then \phi(ab) = \phi(a) \phi(b).[3][2] The modern \phi notation was later adopted by Carl Friedrich Gauss in 1801, while the term "totient" was coined by J. J. Sylvester in 1879.[3]
A general formula for the function is \phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right), where the product runs over distinct prime factors p of n.[1][2] Notable properties include that \phi(n) is even for all n \geq 3, the sum of \phi(d) over all positive divisors d of n equals n, and \phi(n) represents the order of the multiplicative group of integers modulo n, i.e., the number of units in the ring \mathbb{Z}/n\mathbb{Z}.[1][2] Additionally, \phi(n) \geq \sqrt{n} for all n except n=2 and n=6.[1]
The function plays a central role in Euler's theorem, which states that if \gcd(a, n) = 1, then a^{\phi(n)} \equiv 1 \pmod{n}, generalizing Fermat's Little Theorem.[4] It also appears in the Dirichlet generating function \sum_{n=1}^\infty \frac{\phi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)} for \Re(s) > 2, linking it to the Riemann zeta function.[1] Applications extend to geometry, such as determining the number of constructible regular polygons, and to modern cryptography, where it underpins the security of algorithms like RSA by facilitating computations in modular arithmetic.[3]
Definition
Euler's totient function, denoted \phi(n), where n is a positive integer, counts the number of positive integers k satisfying $1 \leq k \leq n and \gcd(n, k) = 1.[5] This function was first introduced by Leonhard Euler in his 1763 paper Theoremata arithmetica nova methodo demonstrata.[6]
For the specific case n = 1, \phi(1) = 1, as the only integer in the range is k = 1 and \gcd(1, 1) = 1.[1]
Geometric interpretation
The geometric interpretation of Euler's totient function \phi(n) provides an intuitive understanding of its role in counting integers coprime to n, by viewing it through the lens of lattice points in the plane that are "visible" from the origin. A lattice point (x, y) with integer coordinates is visible from the origin if the line segment connecting them contains no other lattice points, which holds precisely when \gcd(x, y) = 1.[7]
Consider the horizontal line at height y = n in the integer lattice, specifically the segment from (1, n) to (n, n). The lattice points on this segment are (k, n) for k = 1, 2, \dots, n. Among these, the points visible from the origin are exactly those where \gcd(k, n) = 1, because if \gcd(k, n) = d > 1, then the point (k/d, n/d) lies on the segment between the origin and (k, n). Thus, there are precisely \phi(n) such visible points, and the ratio \phi(n)/n represents the proportion of lattice points on this line segment that are visible from the origin. This perspective highlights how \phi(n) quantifies the "primitive" directions along a fixed height aligned with n.[8]
For a concrete illustration with n = 6, where \phi(6) = 2, the lattice points on the line y = 6 from x = 1 to x = 6 are (1,6), (2,6), (3,6), (4,6), (5,6), and (6,6). The visible ones are (1,6) and (5,6), as \gcd(1,6) = 1 and \gcd(5,6) = 1, whereas the others have \gcd > 1 (e.g., \gcd(2,6) = 2, \gcd(3,6) = 3). This shows \phi(6)/6 = 2/6 = 1/3 as the visibility proportion along that segment.[8]
Complementing this geometric view, \phi(n)/n admits a probabilistic interpretation: it equals the probability that a randomly selected integer k from \{1, 2, \dots, n\} satisfies \gcd(k, n) = 1. This framing underscores the function's connection to the likelihood of coprimality within a finite set modulo n, without relying on explicit counting mechanisms.
Properties
Multiplicativity
A function f defined on the positive integers is called multiplicative if f(1) = 1 and f(ab) = f(a)f(b) whenever \gcd(a, b) = 1. Euler's totient function \phi(n) satisfies this property: if \gcd(m, n) = 1, then \phi(mn) = \phi(m)\phi(n).[1][9]
To see why, consider the sets of integers coprime to m, n, and mn. The Chinese Remainder Theorem implies that the ring \mathbb{Z}/mn\mathbb{Z} is isomorphic to the product ring \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} when \gcd(m, n) = 1. This isomorphism induces a bijection between the units in \mathbb{Z}/mn\mathbb{Z} (which has cardinality \phi(mn)) and the pairs of units in \mathbb{Z}/m\mathbb{Z} and \mathbb{Z}/n\mathbb{Z} (with cardinalities \phi(m) and \phi(n), respectively). Thus, \phi(mn) equals the product \phi(m)\phi(n).[1][9]
This multiplicativity has key implications for computing \phi(n) when n factors into coprime parts, as it allows the value to be obtained by multiplying the totients of those parts rather than counting residues modulo the full n. For example, since \gcd(3, 5) = 1, \phi(15) = \phi(3)\phi(5) = (3-1)(5-1) = 2 \times 4 = 8.[1]
Relation to Euler's theorem
Euler's theorem in number theory states that if a and n are coprime positive integers, then a^{\phi(n)} \equiv 1 \pmod{n}. This result generalizes Fermat's little theorem, which applies specifically when n is prime. The theorem provides a key tool for simplifying exponentiation in modular arithmetic, where the exponent can be reduced modulo \phi(n) under the coprimality condition.[3]
The totient function \phi(n) plays a central role in this theorem as it equals the order of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^\times, consisting of the residue classes modulo n that are coprime to n. In group theory terms, Euler's theorem follows from Lagrange's theorem, which asserts that the order of any element in a finite group divides the order of the group; thus, raising any unit a modulo n to the power \phi(n) yields the identity element 1 modulo n. The multiplicativity of \phi(n) further supports this structure for composite n, as the group decomposes into a direct product of its Sylow subgroups corresponding to the prime factors of n.[10]
Leonhard Euler introduced the totient function in his 1763 paper "Demonstration of a new method in the theory of arithmetic" to establish this generalization, counting the residues coprime to n to determine the exponent in the congruence. He derived the theorem by considering the cyclic permutations of these coprime residues under multiplication by a, leading to the identity after \phi(n) steps.[3]
For example, take n = 7, where \phi(7) = 6. For a = 2, which is coprime to 7, $2^6 = 64 \equiv 1 \pmod{7} since $64 - 9 \times 7 = 1. This illustrates the theorem's action in reducing exponents within the multiplicative group modulo 7.[10]
The explicit product formula for Euler's totient function \phi(n), where n > 0 has the prime factorization n = \prod_{i=1}^r p_i^{k_i} with distinct primes p_i and exponents k_i \geq 1, is
\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right),
where the product runs over the distinct prime factors p of n.[11]
This formula arises as a building block from the case of prime powers. For n = p^k with prime p and integer k \geq 1,
\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1),
which counts the integers from 1 to p^k excluding the p^{k-1} multiples of p.[12] Substituting into the general case yields the product form, as \phi is multiplicative for coprime arguments, allowing \phi(n) to factor over the prime powers in the factorization of n.[13]
The derivation of the product formula follows directly from the principle of inclusion-exclusion applied to counting integers up to n that share no common prime factors with n. Let S = \{1, 2, \dots, n\} and let the distinct primes dividing n be p_1, \dots, p_r. For each i, define A_i \subseteq S as the set of multiples of p_i in S, so |A_i| = \lfloor n / p_i \rfloor = n / p_i since p_i \mid n. More generally, for a subset I \subseteq \{1, \dots, r\},
\left| \bigcap_{i \in I} A_i \right| = \frac{n}{\prod_{i \in I} p_i}.
The number of elements in S sharing a prime factor with n is then
\sum_i |A_i| - \sum_{i < j} |A_i \cap A_j| + \cdots + (-1)^{r+1} \left| \bigcap_{i=1}^r A_i \right|,
so
\phi(n) = n - \sum_i |A_i| + \sum_{i < j} |A_i \cap A_j| - \cdots + (-1)^r \left| \bigcap_{i=1}^r A_i \right| = n \prod_{i=1}^r \left(1 - \frac{1}{p_i}\right),
as the inclusion-exclusion expansion factors into the product.[11]
For example, if n = 12 = 2^2 \cdot 3, then \phi(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4.[12]
One fundamental identity involving Euler's totient function \phi(n) is the divisor sum formula, which states that for any positive integer n,
\sum_{d \mid n} \phi(d) = n.
This identity arises from a partitioning of the set \{1, 2, \dots, n\}. For each divisor d of n, consider the subset of integers k in this set such that \gcd(k, n) = d. If \gcd(k, n) = d, then k = d \ell where \gcd(\ell, n/d) = 1 and $1 \leq \ell \leq n/d. The number of such \ell is precisely \phi(n/d). Summing over all divisors d of n thus counts each of the n integers exactly once, yielding the identity.[14]
For example, when n = 6, the divisors are 1, 2, 3, and 6, and \phi(1) + \phi(2) + \phi(3) + \phi(6) = 1 + 1 + 2 + 2 = 6. This relation holds multiplicatively for coprime factors, consistent with the totient function's properties.[14]
The divisor sum identity connects directly to the Möbius inversion formula in number theory. Applying Möbius inversion to the relation \sum_{d \mid n} \phi(d) = n yields an explicit expression for \phi(n):
\phi(n) = \sum_{d \mid n} \mu(d) \frac{n}{d},
where \mu is the Möbius function, defined as \mu(d) = 1 if d is square-free with an even number of prime factors, \mu(d) = -1 if odd, and \mu(d) = 0 otherwise. This inversion provides a combinatorial way to compute \phi(n) by inclusion-exclusion over the prime factors of n.[14]
A key asymptotic result concerns the summatory function \sum_{k=1}^m \phi(k), which represents the total number of fractions a/b with $1 \leq b \leq m and \gcd(a, b) = 1. As m \to \infty,
\sum_{k=1}^m \phi(k) \sim \frac{3 m^2}{\pi^2},
with an error term of O(m \log m). This asymptotic reflects the average order of \phi(k), approximately \frac{6 k}{\pi^2}, derived from the Euler product for the Riemann zeta function at s=2, where \zeta(2) = \pi^2 / 6. The constant $3 / \pi^2 quantifies the density of integers coprime to their denominators up to m.[14]
Computation
Direct evaluation
The most straightforward method to compute Euler's totient function φ(n) is the naive counting approach, which iterates over all integers k from 1 to n-1 and counts those for which the greatest common divisor gcd(n, k) equals 1.[15] This method directly implements the definition of φ(n) as the number of integers up to n that are coprime to n.[12] The time complexity of this approach is O(n log n), arising from n iterations each requiring a gcd computation that takes O(log n) time via the Euclidean algorithm.[16]
A more efficient direct evaluation method relies on first factorizing n into its prime factors and then applying the product formula φ(n) = n ∏_{p|n} (1 - 1/p), where the product is over the distinct prime factors p of n.[12] Factorization can be performed using trial division by checking divisibility from 2 up to √n, which has a time complexity of O(√n).[17] Once the primes are identified, the formula computes φ(n) in O(ω(n)) additional time, where ω(n) is the number of distinct prime factors, typically small.[12]
For example, to compute φ(100), first factorize 100 as 2² × 5² using trial division up to √100 ≈ 10. The distinct primes are 2 and 5, so φ(100) = 100 × (1 - 1/2) × (1 - 1/5) = 100 × ½ × ⁴/₅ = 40.[12] This yields the count of integers up to 100 coprime to 100, such as 1, 3, 7, 9, 11, and so on.[17]
These direct methods are suitable for small n but become inefficient for large n due to the O(n log n) cost of the naive approach and the O(√n) bottleneck in factorization, limiting practicality without further optimizations.[16][17]
Efficient algorithms
One efficient approach for computing Euler's totient function φ(k) for all integers k from 1 to m involves a variant of the Sieve of Eratosthenes, which processes multiples of each prime and updates the totient values in a single pass.[17] This method initializes an array φ where φ = i for i = 1 to m, then iterates over potential primes i from 2 to m; if φ remains i (indicating i is prime), it updates all multiples j = i, 2i, ..., up to m by setting φ ← φ * (1 - 1/i), or equivalently φ ← φ - φ/i to avoid floating-point operations.[17] The time complexity is O(m log log m), matching the harmonic sum of prime multiples, making it suitable for precomputing totients over a range without repeated factorizations.[17]
For even faster precomputation over ranges up to m, the linear sieve extends this idea by generating primes and composites in linear time while simultaneously computing φ values, ensuring each number is visited only once per prime factor.[18] It maintains lists of primes and marks composites using the smallest prime factor, setting φ = p - 1 for primes p; for a composite x = i * p (where p is the next prime), if p divides i then φ = p * φ, else φ = φ * (p - 1).[18] This achieves O(m) time complexity by avoiding redundant updates, ideal for applications requiring totients for all k ≤ m, such as batch computations in number-theoretic algorithms.[18]
For a single large integer n where direct sieving is infeasible due to size, computing φ(n) requires first finding its prime factorization, after which the product formula φ(n) = n ∏_{p|n} (1 - 1/p) can be applied directly.[19] Efficient factorization methods for such n include Pollard's rho algorithm, a probabilistic Monte Carlo technique that generates a pseudo-random sequence modulo n using a polynomial like f(x) = x² + c mod n and detects non-trivial factors via cycle detection with Floyd's tortoise-and-hare method, running in expected O(√p) time where p is the smallest prime factor of n.[19] Alternatively, the elliptic curve method (ECM) can be used for numbers with moderately large factors, adapting elliptic curve arithmetic over finite fields to find splits in the factorization.[19]
To illustrate the sieve variant, consider computing φ(k) for k = 1 to 10. Initialize φ = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. For i=2 (prime), update multiples: φ[20] ← 2 - 2/2 = 1; φ[21] ← 4 - 4/2 = 2; φ[22] ← 6 - 6/2 = 3; φ[23] ← 8 - 8/2 = 4; φ[24] ← 10 - 10/2 = 5. For i=3 (prime), update: φ[25] ← 3 - 3/3 = 2; φ[22] ← 3 - 3/3 = 2; φ[26] ← 9 - 9/3 = 6. For i=5 (prime), update: φ[27] ← 5 - 5/5 = 4; φ[24] ← 5 - 5/5 = 4. Higher i up to 10 yield no new primes or updates beyond multiples already processed. The final array is φ = [0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4], matching known values like φ[21] = 2 (coprime: 1,3) and φ[23] = 4 (coprime: 1,3,5,7).[17]
pseudocode
function sieve_phi(m):
phi = array of size m+1
for i from 0 to m:
phi[i] = i
for i from 2 to m:
if phi[i] == i: // i is prime
for j = i; j <= m; j += i:
phi[j] = phi[j] - phi[j] / i
return phi
function sieve_phi(m):
phi = array of size m+1
for i from 0 to m:
phi[i] = i
for i from 2 to m:
if phi[i] == i: // i is prime
for j = i; j <= m; j += i:
phi[j] = phi[j] - phi[j] / i
return phi
Special values
Values for primes and prime powers
For a prime number p, the value of Euler's totient function is \phi(p) = p - 1, as all positive integers from 1 to p-1 are relatively prime to p.[1]
For a prime power p^k where p is prime and k \geq 1, the totient function gives \phi(p^k) = p^k - p^{k-1}, since the integers from 1 to p^k that are not relatively prime to p^k are precisely the multiples of p, and there are p^{k-1} such multiples.[1] This can equivalently be written as \phi(p^k) = p^{k-1}(p - 1).[1]
The following table illustrates these values for small primes and their powers:
| n | Prime power form | \phi(n) |
|---|
| 2 | $2^1 | 1 |
| 3 | $3^1 | 2 |
| 4 | $2^2 | 2 |
| 5 | $5^1 | 4 |
| 7 | $7^1 | 6 |
| 8 | $2^3 | 4 |
| 9 | $3^2 | 6 |
| 11 | $11^1 | 10 |
| 16 | $2^4 | 8 |
| 25 | $5^2 | 20 |
Values for common integers
The values of Euler's totient function φ(n) for small composite integers illustrate its computation and patterns, often leveraging multiplicativity: for coprime m and k, φ(mk) = φ(m)φ(k).[1] For instance, φ(10) = φ(2 × 5) = φ(2)φ(5) = 1 × 4 = 4, counting the integers 1, 3, 7, 9 coprime to 10. Similarly, φ(12) = φ(4 × 3) = φ(4)φ(3) = 2 × 2 = 4, with coprimes 1, 5, 7, 11, showing that distinct n can yield the same φ(n).[28] As n grows, φ(n) generally increases but with fluctuations, such as φ(30) = 8 versus φ(60) = 16, reflecting the influence of prime factors.[28]
The following table lists φ(n) for n from 1 to 20, along with selected larger composites like 24, 30, and 60, computed via the standard formula φ(n) = n ∏_{p|n} (1 - 1/p) over distinct primes p dividing n.[1]
| n | φ(n) |
|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 4 |
| 6 | 2 |
| 7 | 6 |
| 8 | 4 |
| 9 | 6 |
| 10 | 4 |
| 11 | 10 |
| 12 | 4 |
| 13 | 12 |
| 14 | 6 |
| 15 | 8 |
| 16 | 8 |
| 17 | 16 |
| 18 | 6 |
| 19 | 18 |
| 20 | 8 |
| 24 | 8 |
| 30 | 8 |
| 60 | 16 |
Applications
In number theory
The Euler totient function φ(n) generalizes Fermat's Little Theorem, which states that if p is prime and gcd(a, p) = 1, then a^{p-1} ≡ 1 \pmod{p}. Since φ(p) = p-1 for prime p, Fermat's Little Theorem is a special case of Euler's theorem, which asserts a^{φ(n)} ≡ 1 \pmod{n} whenever gcd(a, n) = 1.[30]
In the study of primitive roots, Artin's conjecture posits that for any integer a neither -1 nor a perfect square, there are infinitely many primes p such that a is a primitive root modulo p, meaning the order of a modulo p is exactly p-1. The conjecture predicts that the natural density of such primes is the Artin constant A ≈ 0.3739558, given by the infinite product A = \prod_{p \geq 2} \left(1 - \frac{1}{p(p-1)}\right) over primes p. This density arises from probabilistic considerations involving the factorization of p-1, as the number of primitive roots modulo p is precisely φ(p-1), the count of generators of the multiplicative group modulo p.[31]
The totient function also determines the constructibility of regular polygons. By the Gauss–Wantzel theorem, a regular n-gon can be constructed with straightedge and compass if and only if φ(n) is a power of 2. This condition ensures that the degree of the cyclotomic extension \mathbb{Q}(\zeta_n)/\mathbb{Q} is a power of 2, allowing ruler-and-compass construction via iterated quadratic extensions.[32]
Dirichlet's class number formula for quadratic fields connects the totient function to algebraic number theory through Dirichlet L-functions. For an imaginary quadratic field \mathbb{Q}(\sqrt{d}) with fundamental discriminant d < -4, the class number h satisfies h = \frac{\sqrt{|d|}}{\pi} L(1, \chi_d), where \chi_d is the quadratic Dirichlet character modulo |d| given by the Kronecker symbol (d / \cdot), and L(s, \chi_d) = \sum_{n=1}^\infty \chi_d(n) n^{-s}. The characters modulo |d| form a group isomorphic to (\mathbb{Z}/|d|\mathbb{Z})^\times, whose order is φ(|d|), thus the totient function determines the structure and count of these characters underlying the L-function in the formula.[33]
The totient function also features in proofs of the infinitude of primes via Euler products and properties of the Riemann zeta function. The Dirichlet series \sum_{n=1}^\infty \frac{\phi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)} for \Re(s) > 2 links φ(n) to the zeta function, whose Euler product \zeta(s) = \prod_p (1 - p^{-s})^{-1} over primes p encodes the prime distribution; the divergence of \zeta(s) as s \to 1^+ implies infinitely many primes. The identity n = \sum_{d \mid n} \phi(d) implies via partial summation that the partial sums of the series at s=1 grow asymptotically as \frac{6 x}{\pi^2}, and this linear divergence is consistent with the infinitude of primes.[34] The summatory function \sum_{n \leq x} \phi(n) \sim \frac{3x^2}{\pi^2} provides key estimates in such analytic arguments for prime counting.
In cryptography
The Euler totient function plays a central role in the RSA cryptosystem, where it is used to generate the private key from the public key. In RSA, a modulus n = pq is formed from two large distinct primes p and q, and the totient \phi(n) = (p-1)(q-1) is computed privately. A public encryption exponent e is chosen such that $1 < e < \phi(n) and \gcd(e, \phi(n)) = 1, and the private decryption exponent d satisfies ed \equiv 1 \pmod{\phi(n)}, allowing decryption via c^d \mod n for ciphertext c.[35]
The security of RSA hinges on the difficulty of factoring n into p and q, which equivalently protects \phi(n) from computation by unauthorized parties. If \phi(n) were exposed for a semiprime n = pq, the factors could be recovered deterministically by solving the quadratic equation derived from p + q = n - \phi(n) + 1 and pq = n, compromising the entire key.[35][36] This equivalence in computational complexity ensures that attacks on RSA reduce to the integer factorization problem.[37]
In the Diffie-Hellman key exchange protocol, \phi(n) bounds the order of the multiplicative group modulo n, influencing the selection of safe primes and subgroup sizes to prevent small-subgroup attacks. For a prime modulus p, the group order is \phi(p) = p-1, and generators are chosen from subgroups whose orders divide p-1 to ensure discrete logarithm hardness.[38][39]
For example, in a toy RSA instance with n = 15 = 3 \times 5, \phi(15) = 8, so e = 3 yields d = 11 since $3 \times 11 = 33 \equiv 1 \pmod{8}; however, practical RSA keys employ semiprimes with thousands of bits to resist factoring.[35] RSA's correctness stems from Euler's theorem, which guarantees that for \gcd(m, n) = 1, m^{\phi(n)} \equiv 1 \pmod{n}, enabling the modular inverse computation for decryption.[35]
History
Discovery by Euler
Leonhard Euler introduced the totient function during the 1760s as part of his investigations into arithmetic properties and generalizations of Fermat's little theorem. In his paper "Theoremata arithmetica nova methodo demonstrata," written in 1758 and published in 1763, Euler defined the function verbally as the "multitude of numbers less than N which are prime to N," counting the positive integers up to n that are coprime to n. This work marked the first systematic study of the function, motivated by Euler's efforts to establish a general congruence theorem for integers coprime to the modulus.[40]
Euler's key contributions in this paper included deriving explicit formulas for the function's values. He proved that for a prime p and positive integer m, the totient equals p^m - p^{m-1}, and demonstrated its multiplicativity: if a and b are coprime, then the totient of ab is the product of the totients of a and b. These results enabled the general formula for any n based on its prime factorization. Additionally, Euler established the fundamental identity that the sum of the totient over all positive divisors d of n equals n, providing a pivotal relation that connected the function to the divisor structure of integers. This proof relied on partitioning the integers from 1 to n according to their greatest common divisor with n.[40]
A significant insight from Euler's era linked the totient function to cyclotomic polynomials, which arise in the factorization of x^n - 1. The degree of the nth cyclotomic polynomial is precisely φ(n), reflecting the number of primitive nth roots of unity. This connection emerged from Euler's studies on polynomial factorizations and regular polygons, where the totient quantifies the primitive elements in cyclic groups. Although Euler did not introduce a dedicated symbol—using descriptive language instead—his work laid the groundwork for later notations like π(n) in his 1775 manuscript published in 1784. These developments coincided with his formulation of what is now known as Euler's theorem on congruences, stating that if a and n are coprime, then a^{φ(n)} ≡ 1 mod n.[40]
Later developments
In the early 19th century, Carl Friedrich Gauss advanced the study of the totient function in his seminal work Disquisitiones Arithmeticae (1801), where he introduced the notation \phi(n) and employed it in the development of the law of quadratic reciprocity, particularly in analyzing the structure of quadratic residues modulo primes.[41] Gauss's treatment highlighted the totient's role in counting the units in the ring of integers modulo n, laying foundational connections to reciprocity laws in number theory.
During the 20th century, significant progress included W. Sierpiński's 1933 conjecture that for every integer k \geq 1, there exists an m such that the equation \phi(x) = m has exactly k solutions x, addressing the distribution and multiplicity of totient values—a problem resolved affirmatively by Kevin Ford in 1999.[42] Complementing this, Robert D. Carmichael introduced the lambda function \lambda(n) in 1910 as the exponent of the multiplicative group modulo n, which divides \phi(n) and serves as a universal exponent for Euler's theorem, refining applications in group orders and pseudoprime detection.
In modern developments, sharper bounds on \phi(n)/n have been established, with Jean-Louis Nicolas proving in 1983 that \phi(n) > c \frac{n}{\log \log n} for some absolute constant c > 0 and all n \geq 3, improving prior estimates and linking small totient values to the Riemann hypothesis via primorials.[43] This bound underscores the totient's minimal growth relative to n, with equality nearly attained at products of the first k primes.
Ongoing research features unsolved problems, such as refinements to the precise average order of \phi(n), where the summatory function \sum_{k=1}^n \phi(k) = \frac{3n^2}{\pi^2} + E(n) has an error term E(n) whose optimal asymptotic remains open beyond subpolynomial improvements by later analysts. Questions on totient injectivity, including whether certain multiplicity patterns persist under restrictions (e.g., odd totients), continue to challenge the function's inverse image structure.