Carmichael function
The Carmichael function, denoted \lambda(n), is a function in number theory that assigns to each positive integer n the smallest positive integer m such that a^m \equiv 1 \pmod{n} for every integer a coprime to n.[1] It represents the exponent of the multiplicative group of integers modulo n, also known as the universal exponent or reduced totient function.[2] Introduced by American mathematician Robert D. Carmichael in 1910 to generalize aspects of Fermat's Little Theorem and facilitate the study of primitive roots, the function provides a tighter bound than Euler's totient function \phi(n) for the orders of elements in this group.[1]
For a prime power p^k where p is an odd prime, \lambda(p^k) = \phi(p^k) = p^{k-1}(p-1); for powers of 2, \lambda(1) = 1, \lambda(2) = 1, \lambda(4) = 2, and \lambda(2^k) = 2^{k-2} for k \geq 3.[2] In general, if n = \prod p_i^{k_i} is the prime factorization of n, then \lambda(n) is the least common multiple of the values \lambda(p_i^{k_i}) over all prime powers dividing n.[3] This construction ensures that \lambda(n) always divides \phi(n), with equality holding if and only if n = 1, $2, $4, p^k, or $2p^k where p is an odd prime and k \geq 1.[2][4]
The function plays a key role in analytic number theory, the study of pseudoprimes, and cryptographic protocols such as RSA, where the security relies on the factorization of n = pq and properties of \lambda(n) to determine the order of the group (\mathbb{Z}/n\mathbb{Z})^*.[3] It also appears in investigations of the distribution of values of \lambda(n) and its relation to the Riemann zeta function through connections with \phi(n).[5]
Introduction and Definition
Definition
The Carmichael function, denoted \lambda(n), arises in the context of modular arithmetic, where two integers are congruent modulo n if their difference is divisible by n, and two integers are coprime if their greatest common divisor is 1. For each positive integer n, \lambda(n) is defined as the smallest positive integer m such that a^m \equiv 1 \pmod{n} for every integer a that is coprime to n, with the convention that \lambda(1) = 1.
This function \lambda(n) can be interpreted group-theoretically as the exponent of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^*, which consists of the residue classes modulo n that are coprime to n, equipped with multiplication modulo n. The exponent of a finite abelian group is the least common multiple of the orders of all its elements, where the order of an element g is the smallest positive integer k such that g^k = 1. Thus, \lambda(n) = \exp((\mathbb{Z}/n\mathbb{Z})^*).[2]
It is known that \lambda(n) divides Euler's totient function \phi(n), which counts the number of integers up to n that are coprime to n.[2]
Historical background
The Carmichael function was introduced by American mathematician Robert D. Carmichael in 1910 as part of his research into the properties of abelian groups in number theory. In his seminal paper "Note on a New Number Theory Function," presented to the American Mathematical Society in 1909 and published the following year, Carmichael defined the function to address the exponent of the multiplicative group of integers modulo n, denoted (\mathbb{Z}/n\mathbb{Z})^*. This work arose within studies of the group's structure, particularly in generalizing Fermat's Little Theorem to composite moduli, where the exponent represents the least common multiple of the orders of all elements in the group.[6]
Carmichael's function refined Euler's totient function \phi(n) by focusing specifically on the group's exponent, providing a tool to determine the smallest positive integer m such that a^m \equiv 1 \pmod{n} for all integers a coprime to n. This addressed limitations of \phi(n), which measures the group's order but not always its precise exponent, especially for powers of 2. Early references to the function appeared in subsequent group theory literature, building on Carmichael's contributions to abelian group decompositions and their arithmetic applications.[6]
By the mid-20th century, the function had become a standard concept in number theory, integrated into textbooks for its utility in analyzing multiplicative orders and group exponents. For example, Ireland and Rosen's A Classical Introduction to Modern Number Theory (1982) devoted sections to its properties and computations, underscoring its foundational role in modern algebraic number theory.
Computation of the Carmichael Function
The Carmichael function \lambda(n) for a prime power n = p^k, where p is prime and k \geq 1, is defined as the exponent of the multiplicative group of integers modulo p^k, i.e., the smallest positive integer m such that a^m \equiv 1 \pmod{p^k} for all a coprime to p^k.[7]
For an odd prime p, the group (\mathbb{Z}/p^k\mathbb{Z})^\times is cyclic of order \phi(p^k) = p^{k-1}(p-1), where \phi is Euler's totient function; thus, the exponent equals the group order, yielding
\lambda(p^k) = p^{k-1}(p-1).
For example, \lambda(5) = 4 and \lambda(25) = 20.[7]
For p = 2, the formulas differ by case:
\lambda(2) = 1, \quad \lambda(4) = 2, \quad \lambda(2^k) = 2^{k-2} \quad (k \geq 3).
For instance, \lambda(8) = 2 and \lambda(16) = 4. This reflects the structure of (\mathbb{Z}/2^k\mathbb{Z})^\times, which is isomorphic to \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{k-2}\mathbb{Z} for k \geq 3; the exponent is then the least common multiple of the orders $2 and $2^{k-2}, which is $2^{k-2}.[7][8]
These prime power values serve as the basis for computing \lambda(n) for general n via the least common multiple over its prime power factors.[7]
For a positive integer n > 1 with prime factorization n = \prod_{i=1}^m p_i^{k_i}, where the p_i are distinct primes and each k_i \geq 1, the Carmichael function is defined by
\lambda(n) = \operatorname{lcm} \bigl[ \lambda(p_1^{k_1}), \lambda(p_2^{k_2}), \dots, \lambda(p_m^{k_m}) \bigr].
This formula expresses \lambda(n) in terms of the values \lambda(p_i^{k_i}) for the prime power factors of n, as computed using the definitions for prime powers.[2][9]
The multiplicative group of integers modulo n, denoted (\mathbb{Z}/n\mathbb{Z})^\times, is isomorphic to the direct product \prod_{i=1}^m (\mathbb{Z}/p_i^{k_i}\mathbb{Z})^\times by the Chinese Remainder Theorem, since the prime power moduli are pairwise coprime. The exponent of a finite direct product of groups equals the least common multiple of the exponents of the factors; thus, \lambda(n) is the lcm of the individual exponents \lambda(p_i^{k_i}).[2]
When n includes a power of 2, the formula applies directly via the lcm, accounting for the adjusted definition \lambda(2^k) = 2^{k-2} for k \geq 3, while the odd prime power components follow \lambda(p^k) = (p-1)p^{k-1}. This ensures \lambda(n) captures the universal exponent across the group structure without further modification.[2]
Recurrence relations
The Carmichael function \lambda(n) can be computed recursively by leveraging its multiplicativity: if m and n are coprime positive integers, then \lambda(mn) = \operatorname{lcm}(\lambda(m), \lambda(n)). This property allows decomposition of n into coprime factors and iterative application of the least common multiple to obtain \lambda(n). For a general composite n, the recurrence proceeds by reducing to the prime power factors, computing \lambda for each, and taking the lcm across them.[10]
A practical iterative scheme separates the power of 2 from the odd part of n. Write n = 2^k \cdot m where m is odd; then \lambda(n) = \operatorname{lcm}(\lambda(2^k), \lambda(m)). The value \lambda(m) is obtained by further decomposing m into its odd prime power factors and taking the lcm of their individual \lambda values, continuing recursively until reaching prime powers.[10] This approach exploits the Chinese Remainder Theorem structure of the multiplicative group modulo n, ensuring the exponent is the lcm of the exponents modulo the factors.
The iterative computation of \lambda(n) parallels that of Euler's totient function \phi(n), but highlights key differences: while \phi(n) is the product of contributions from each prime power, \lambda(n) uses the lcm, which often yields a smaller value since it captures the minimal universal exponent rather than the group order. For example, the recursion for \phi(n) multiplies terms like p^{k-1}(p-1), whereas for \lambda(n), the lcm operation may halve certain powers of 2 or align cycles more tightly, reflecting the reduced requirements for exponentiation in the group (\mathbb{Z}/n\mathbb{Z})^\times.[10]
Algorithmically, computing \lambda(n) is efficient given the prime factorization of n, which can be obtained in subexponential time for practical sizes. The following pseudocode outlines an iterative implementation assuming a factorization function factor(n) returns a list of prime-power pairs (p, k):
function carmichael_lambda(n):
if n == 1: return 1
factors = factor(n)
lambda_values = []
for (p, k) in factors:
lambda_pk = lambda_prime_power(p, k) // Compute λ(p^k) using base cases
lambda_values.append(lambda_pk)
result = lambda_values[0]
for i = 1 to len(lambda_values)-1:
result = lcm(result, lambda_values[i])
return result
// lcm(a, b) = a * b / gcd(a, b)
function carmichael_lambda(n):
if n == 1: return 1
factors = factor(n)
lambda_values = []
for (p, k) in factors:
lambda_pk = lambda_prime_power(p, k) // Compute λ(p^k) using base cases
lambda_values.append(lambda_pk)
result = lambda_values[0]
for i = 1 to len(lambda_values)-1:
result = lcm(result, lambda_values[i])
return result
// lcm(a, b) = a * b / gcd(a, b)
This method scales well for cryptographic or number-theoretic applications, with the dominant cost in factorization.[10]
Examples and Values
Numerical examples
The Carmichael function \lambda(n) is evaluated for small values of n by applying its defining formulas based on the prime factorization of n. For n=1, \lambda(1)=1, as the multiplicative group modulo 1 is trivial.[2] For prime n=5, \lambda(5)=4, matching the order of the group (\mathbb{Z}/5\mathbb{Z})^\times.[2] Similarly, for n=7, \lambda(7)=6.[2]
For powers of primes, consider n=8=2^3. Here, \lambda(8)=2, which is half the Euler totient \phi(8)=4, reflecting the adjustment for powers of 2 greater than or equal to 8.[2] For n=9=3^2, \lambda(9)=\phi(9)=6.[2] For the product n=10=2 \times 5, \lambda(10)=\operatorname{lcm}(\lambda(2),\lambda(5))=\operatorname{lcm}(1,4)=4.[2]
A detailed computation arises for composite n=15=3 \times 5. First, \lambda(3)=2 and \lambda(5)=4, so \lambda(15)=\operatorname{lcm}(2,4)=4.[2] This value satisfies the defining property: for a=2 coprime to 15, $2^4=16 \equiv 1 \pmod{15}, and similarly for other residues like a=4 or a=7. In contrast to Euler's totient \phi(15)=8, \lambda(15)=4 < \phi(15), highlighting that \lambda(n) is the minimal such exponent.[2]
Additional examples include n=16=2^4, where \lambda(16)=4=2^{4-2}, and n=21=3 \times 7, where \lambda(21)=\operatorname{lcm}(\lambda(3),\lambda(7))=\operatorname{lcm}(2,6)=6.[2]
Small values and tables
The following table presents the values of the Carmichael function λ(n) alongside Euler's totient function φ(n) for n from 1 to 50, illustrating their relationship for small arguments.[11][12]
| n | λ(n) | φ(n) |
|---|
| 1 | 1 | 1 |
| 2 | 1 | 1 |
| 3 | 2 | 2 |
| 4 | 2 | 2 |
| 5 | 4 | 4 |
| 6 | 2 | 2 |
| 7 | 6 | 6 |
| 8 | 2 | 4 |
| 9 | 6 | 6 |
| 10 | 4 | 4 |
| 11 | 10 | 10 |
| 12 | 2 | 4 |
| 13 | 12 | 12 |
| 14 | 6 | 6 |
| 15 | 4 | 8 |
| 16 | 4 | 8 |
| 17 | 16 | 16 |
| 18 | 6 | 6 |
| 19 | 18 | 18 |
| 20 | 4 | 8 |
| 21 | 6 | 12 |
| 22 | 10 | 10 |
| 23 | 22 | 22 |
| 24 | 2 | 8 |
| 25 | 20 | 20 |
| 26 | 12 | 12 |
| 27 | 18 | 18 |
| 28 | 6 | 12 |
| 29 | 28 | 28 |
| 30 | 4 | 8 |
| 31 | 30 | 30 |
| 32 | 8 | 16 |
| 33 | 10 | 20 |
| 34 | 16 | 16 |
| 35 | 12 | 24 |
| 36 | 6 | 12 |
| 37 | 36 | 36 |
| 38 | 18 | 18 |
| 39 | 12 | 24 |
| 40 | 4 | 16 |
| 41 | 40 | 40 |
| 42 | 6 | 12 |
| 43 | 42 | 42 |
| 44 | 10 | 20 |
| 45 | 12 | 24 |
| 46 | 22 | 22 |
| 47 | 46 | 46 |
| 48 | 4 | 16 |
| 49 | 42 | 42 |
| 50 | 20 | 20 |
Core Properties
Relation to Euler's totient function
The Carmichael function \lambda(n) divides Euler's totient function \phi(n) for every positive integer n \geq 1.[14] This divisibility relation underscores a fundamental similarity between the two functions: both are intimately tied to the structure of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^*, where \phi(n) denotes the order of the group and \lambda(n) denotes its exponent, defined as the smallest positive integer m such that a^m \equiv 1 \pmod{n} for all a coprime to n.[14]
To see why \lambda(n) divides \phi(n), observe that \lambda(n) is the least common multiple of the orders of all elements in (\mathbb{Z}/n\mathbb{Z})^*. By Lagrange's theorem, the order of any element in a finite group divides the group order; thus, each such order divides \phi(n), and their least common multiple \lambda(n) must also divide \phi(n).[15] This connection highlights a key difference: while \phi(n) measures the total number of units modulo n, \lambda(n) captures the minimal universal exponent for the group's action, often strictly smaller than \phi(n) when the group is non-cyclic.
Equality \lambda(n) = \phi(n) holds if and only if (\mathbb{Z}/n\mathbb{Z})^* is cyclic, in which case the exponent coincides with the group order.[8] The multiplicative group (\mathbb{Z}/n\mathbb{Z})^* is cyclic precisely when n=1, n=2, n=4, n=p^k for an odd prime p and k \geq 1, or n=2p^k for an odd prime p and k \geq 1.[8] In these cases, the functions align perfectly, reflecting the cyclic nature of the group; otherwise, \lambda(n) provides a stricter bound on the exponents needed for modular exponentiation.
Multiplicativity and lcm properties
The Carmichael function \lambda exhibits a form of multiplicativity adapted to its role as the exponent of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^\times. Specifically, if \gcd(a, b) = 1, then \lambda(ab) = \operatorname{lcm}(\lambda(a), \lambda(b)). This property arises because the Chinese Remainder Theorem establishes an isomorphism (\mathbb{Z}/ab\mathbb{Z})^\times \cong (\mathbb{Z}/a\mathbb{Z})^\times \times (\mathbb{Z}/b\mathbb{Z})^\times, and the exponent of a direct product of finite groups is the least common multiple of the exponents of the factors.
This lcm-multiplicativity extends naturally to the prime power factorization of n. For n = \prod_p p^k where the product is over distinct primes p dividing n, \lambda(n) = \operatorname{lcm}_p \lambda(p^k). The function is thus determined by its values on prime powers, with the overall value obtained via successive lcms over coprime components. This composition rule underscores \lambda's utility in computing the universal exponent for composite moduli.
As the universal exponent, \lambda(n) serves as the cycle length for powers of elements coprime to n modulo n: for any a with \gcd(a, n) = 1, a^{\lambda(n)} \equiv 1 \pmod{n}, and \lambda(n) is the smallest positive integer with this property for all such a. This makes \lambda(n) the maximal order of any element in (\mathbb{Z}/n\mathbb{Z})^\times, equivalently the period beyond which the powers of any unit repeat the identity.
Consequences of minimality
The Carmichael function \lambda(n) is defined as the smallest positive integer m such that a^m \equiv 1 \pmod{n} for every integer a coprime to n. This minimality implies that no smaller positive integer satisfies the congruence for all such a, making \lambda(n) the universal exponent of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^*.[16]
As the exponent of this finite abelian group, \lambda(n) equals the least common multiple of the orders of all its elements and, crucially, the maximal order attained by any single element. Thus, there exists at least one a coprime to n whose multiplicative order modulo n is precisely \lambda(n), often termed a primitive \lambda-root modulo n. This maximal order property underscores \lambda(n)'s role as a measure of the group's "complexity," distinguishing it from Euler's totient \phi(n), which counts elements but not their order structure.[16][17]
A direct consequence of this minimality is the completeness of the order lattice within the group: every positive divisor d of \lambda(n) is realized as the order of some element a coprime to n. In other words, for each such d, there exists a with \operatorname{ord}_n(a) = d. This follows from the fundamental theorem of finite abelian groups, which guarantees cyclic subgroups of every order dividing the exponent, ensuring no gaps in the possible orders. Such a structure highlights why \lambda(n) captures the full cyclic decomposition of (\mathbb{Z}/n\mathbb{Z})^* more succinctly than \phi(n).[16]
The minimality of \lambda(n) also ties closely to the existence of primitive roots modulo n. If (\mathbb{Z}/n\mathbb{Z})^* is cyclic, then it possesses a generator of order \phi(n), implying \lambda(n) = \phi(n). Conversely, whenever \lambda(n) = \phi(n), the group must be cyclic, admitting primitive roots. This equality holds exactly when n = 1, 2, 4, p^k, or $2p^k for an odd prime p and positive integer k; in all other cases, \lambda(n) < \phi(n), reflecting the non-cyclic nature of the group. Elements achieving order \lambda(n) in these non-cyclic cases generalize primitive roots and are called primitive \lambda-roots.[16][17]
Finally, the minimality of \lambda(n) informs the study of the inverse problem: finding the smallest positive integer n such that \lambda(n) = k for a given k. This "minimal modulus" for a fixed exponent value k reveals insights into the range and distribution of \lambda, with applications to understanding how \lambda(n) grows relative to n. For instance, such minimal n often involve products of small primes tailored to match the prime power formula for \lambda.[18]
Advanced Properties
Divisibility and composition rules
The Carmichael function \lambda(n) exhibits several key divisibility properties that arise from its role as the exponent of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^\times. For n > 2, \lambda(n) is always even, reflecting the structure of the group where the maximum order is divisible by 2.[19] Additionally, \lambda(n) divides any integer multiple of itself, ensuring that powers congruent to 1 modulo n for coprime bases repeat at multiples of this exponent.[20]
For composition rules involving powers, the value of \lambda(n^k) depends on the prime factorization of n. If n = p_1^{a_1} \cdots p_r^{a_r}, then \lambda(n^k) = \operatorname{lcm} \bigl[ \lambda(p_1^{a_1 k}), \dots, \lambda(p_r^{a_r k}) \bigr]. For odd primes p, \lambda(p^{m}) = \phi(p^{m}) = p^{m-1}(p-1) for any m \geq 1, so \lambda(p^{a k}) = p^{a k - 1}(p-1). For the prime 2, \lambda(2^m) = 2^{m-2} when m \geq 3, \lambda(2) = 1, and \lambda(4) = 2, leading to \lambda(2^{a k}) = 2^{a k - 2} for a k \geq 3. These relations allow computation of \lambda(n^k) by scaling the exponents in the prime power components.[21]
Intervals where \lambda(n) takes specific constant values, known as runs of constant \lambda, occur frequently and can be arbitrarily long. Recent improvements bound the maximal such run length F_\lambda(x) by O((\log x)^{1/0.677}) for large x, using estimates on prime factors in shifted sequences. These prevailing intervals highlight the stepwise nature of \lambda(n)'s growth.[22]
When n has multiple distinct prime factors, the computation of \lambda(n) = \operatorname{lcm} \bigl[ \lambda(p_1^{k_1}), \dots, \lambda(p_r^{k_r}) \bigr] requires adjustments for shared prime factors among the \lambda(p_i^{k_i}). If the individual \lambda(p_i^{k_i}) share common prime divisors, the least common multiple takes the maximum exponent for each prime, potentially reducing \lambda(n) below the product of the components. For instance, if two odd primes p and q both yield \lambda(p^{k}) = (p-1) p^{k-1} and \lambda(q^{m}) = (q-1) q^{m-1} sharing a factor like 2 or another prime in their factorizations, the lcm accounts for the highest power of that shared prime across all terms. This adjustment ensures \lambda(n) captures the precise exponent without redundancy.[21]
Bounds and inequalities
The Carmichael function \lambda(n) satisfies the inequality \lambda(n) \leq \phi(n) for all positive integers n > 1, where \phi denotes Euler's totient function, since \lambda(n) is the exponent of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^\times of order \phi(n), and the order of any element divides the group order. Equality holds precisely when n = 1, 2, 4, p^k, or $2p^k for an odd prime p and integer k \geq 1, as in these cases the group is cyclic or has exponent equal to its order.[23]
For prime powers, explicit forms provide tight bounds: if p is an odd prime and k \geq 1, then \lambda(p^k) = p^{k-1}(p-1) = \phi(p^k); for p=2, \lambda(2) = 1, \lambda(4) = 2, and \lambda(2^k) = 2^{k-2} for k \geq 3, so \lambda(2^k) = \phi(2^k)/2. In particular, for a prime p, \lambda(p) = p-1, which grows linearly with p. For general n, \lambda(n) grows more slowly than n on average but can approach \phi(n) closely for prime-like n.
Elementary lower bounds relate \lambda(n) to \phi(n) via the structure of the prime factorization. Since \lambda(n) = \mathrm{lcm}\{\lambda(p_i^{k_i}) : p_i^{k_i} \| n\} and each \lambda(p_i^{k_i}) is comparable to \phi(p_i^{k_i}), a crude estimate yields \lambda(n) \geq \phi(n) / 2^{\omega(n)}, where \omega(n) is the number of distinct prime factors, though this weakens as \omega(n) increases. Tighter relations follow from the ratio \phi(n)/\lambda(n), which is an integer measuring how much the lcm reduces the product of the \phi(p^k); this ratio equals 1 when equality holds in the upper bound and grows with the shared prime factors among the p-1's.
Advanced results provide asymptotic bounds on the minimal growth of \lambda(n). Erdős, Pomerance, and Schmutz proved that for every constant c < 1/\log 2 \approx 1.4427, there exists N such that \lambda(n) > (\log n)^c \log \log \log n for all n > N. Conversely, there exist constants c' > 0 and infinitely many n such that \lambda(n) < (\log n)^{c'}, showing that \lambda(n) can be as small as a polylogarithmic function of n for some n. These bounds highlight the wide range of possible values, with \lambda(n) typically much larger than logarithmic but occasionally small when n is a product of primes with highly composite p-1.[23]
Asymptotic behavior and average order
The average order of the Carmichael function λ(n) is given by
\frac{1}{x} \sum_{n \le x} \lambda(n) \sim \frac{x}{\log x} \exp\left( B \frac{\log \log x}{\log \log \log x} (1 + o(1)) \right),
where B \approx 0.261497 is an explicit constant defined as B = \exp(\gamma) \prod_p \left(1 + \frac{1}{p(p-1)}\right) with γ the Euler–Mascheroni constant, as established by Erdős, Pomerance, and Schmutz.[18] This asymptotic reflects the dominant contribution from prime n, where λ(p) = p-1 ≈ p, leading to the leading term x / log x scaled by a subexponential factor capturing finer arithmetic structure in the prime factorization of n.
The distribution of λ(n) exhibits notable features for specific relations to the Euler totient φ(n). The proportion of integers n ≤ x for which λ(n) = φ(n) is asymptotic to \frac{c}{\log x} for some constant c > 0 (approximately 1.5), corresponding to the n where the multiplicative group modulo n is cyclic; these n are precisely 1, powers of 2 up to 4, odd prime powers p^k, and twice odd prime powers 2p^k, whose count up to x is ∼ (3/2) x / log x. More generally, the frequency of small values λ(n) ≤ y for n ≤ x, with y fixed or growing slowly, is bounded above by x exp(−c √(log x log log x)) for some c > 0 when y is sufficiently small relative to x, highlighting the rarity of exceptionally small exponents in the multiplicative group.
Prevailing values of λ(n) for n ≤ x tend to cluster around intervals near p-1 for primes p ≈ x, as these arise frequently from prime n and contribute the bulk to the average; secondary clusters occur from semiprimes 2p or prime powers, but the density ensures that values around large prime-minus-one dominate the distribution in scale.[18]
Recent developments have refined bounds on extreme values. For large values, Erdős, Pomerance, and Schmutz showed that λ(n) > (log n)^c for every c < 1/log 2 holds for all but O(x / (log x)^c) exceptions n ≤ x.[18] For the distribution of the range, Ford proved that the number of distinct values in {λ(n) : n ≤ x} is asymptotic to x / (log x)^η with η = 1 - (1 + log log 2)/log 2 ≈ 0.086071, improving prior upper bounds and confirming a heuristic on the image size.[5]
Applications
In cryptography
The Carmichael function λ(n) plays a central role in the RSA cryptosystem, where n is the product of two distinct primes p and q. In RSA key generation, the private exponent d is computed as the modular inverse of the public exponent e modulo λ(n), ensuring that for any message m coprime to n, m^{ed} ≡ m mod n holds, which guarantees correct decryption.[24] Specifically, λ(n) = lcm(λ(p), λ(q)) = lcm(p-1, q-1), providing the exponent of the multiplicative group (ℤ/nℤ)^*.[25]
This use of λ(n) offers efficiency advantages over the Euler totient function φ(n) = (p-1)(q-1), as λ(n) divides φ(n) and is often strictly smaller when p-1 and q-1 share common factors.[26] A smaller modulus for the inverse computation results in a potentially smaller d, which reduces the computational cost of decryption via exponentiation by squaring.[25] Studies show that employing λ(n) can decrease RSA decryption time compared to using φ(n), particularly when p-1 and q-1 share common factors.[27]
From a security perspective, key generation processes must avoid moduli n where λ(n) is unusually small, as such weak values could facilitate attacks by reducing the effective order of the group and exposing vulnerabilities in exponent selection.[28] Modern RSA implementations incorporate checks to ensure λ(n) has sufficiently large prime factors, mitigating risks from smooth or deficient λ(n) that might otherwise compromise key strength.[26]
Beyond RSA, the Carmichael function determines the order of the multiplicative group modulo n in composite-modulus Diffie-Hellman key exchange protocols, where it defines the maximum cycle length for generators and influences the security of discrete logarithm computations. In such settings, selecting n with a large λ(n) ensures the subgroup orders are robust against Pohlig-Hellman attacks.[29]
In pseudorandom generation and number theory
The Carmichael function \lambda(n) determines the maximal order of elements in the multiplicative group of integers modulo n, which directly influences the period of pseudorandom number generators based on exponentiation, known as power generators. In such generators, a sequence is produced via u_{k+1} \equiv u_k^e \pmod{m} for fixed e \geq 2 and modulus m \geq 2, starting from an initial u_0 coprime to m; the period of this sequence divides \lambda(m), achieving the maximum length \lambda(m) if u_0 generates a cyclic component of that order.[30] This property ensures that \lambda(m) sets an upper bound on the cycle length, making it essential for designing generators with sufficiently long periods to mimic randomness. For iterated variants, such as those resembling the Blum-Blum-Shub generator where multiple exponentiations are applied, the effective period relates to the iterated value \lambda(\lambda(m)), which governs the number of cycles in the functional graph of the powering map.[31]
Small values of \lambda(n) are infrequent but critical for assessing generator security, as they can result in unexpectedly short periods, potentially compromising unpredictability in cryptographic applications. Research shows that \lambda(n) is typically on the order of n for most n, but exceptions where \lambda(n) is significantly smaller occur rarely, with precise estimates bounding the count of such n \leq x where \lambda(n) < n^{1-\epsilon} for fixed \epsilon > 0.[32] These findings, derived from analytic number theory tools like sieve methods, highlight how moduli with small \lambda(n) must be avoided in secure implementations to prevent period collapse. Recent work in the 2020s has examined runs of consecutive integers sharing the same \lambda(n) value.[33]
In number theory, \lambda(n) facilitates the study of element orders in (\mathbb{Z}/n\mathbb{Z})^\times, as the order of any a coprime to n divides \lambda(n), providing the exponent of the group and enabling precise analysis of cyclic subgroups. This minimality ensures \lambda(n) is the smallest exponent guaranteeing a^{\lambda(n)} \equiv 1 \pmod{n} for all such a, contrasting with Euler's totient \phi(n) which may overestimate orders. A key application arises with Carmichael numbers, square-free composite integers n satisfying \lambda(n) \mid n-1; this condition implies a^{n-1} \equiv 1 \pmod{n} for all a coprime to n, rendering them absolute Fermat pseudoprimes that evade the Fermat primality test.[34] Such numbers underscore limitations in order-based tests and motivate stronger primality criteria.
Generalizations of Fermat quotients incorporate \lambda(n) to extend primality testing frameworks to composite moduli. The Fermat quotient q_p(a) = (a^{p-1} - 1)/p for prime p and base a coprime to p detects compositeness via non-integral or modular inconsistencies; analogously, the Carmichael quotient C_n(a) = (a^{\lambda(n)} - 1)/n is an integer under the same coprimality, satisfying additive properties like C_n(ab) \equiv C_n(a) + C_n(b) \pmod{n} for coprime a, b. These quotients enable sequence constructions for probabilistic tests, where deviations from expected behaviors signal compositeness, building on the group's exponent for more robust verification than Fermat's alone.
Proofs
Carmichael's main theorems
In his 1910 paper, Robert D. Carmichael introduced the function λ(n), defined as the exponent of the multiplicative group of integers modulo n, which is the smallest positive integer m such that a^m \equiv 1 \pmod{n} for every integer a coprime to n.[1] This function generalizes Euler's totient function φ(n), as λ(n) divides φ(n) and provides a tighter bound on the order of elements in the group, extending Fermat's Little Theorem (where λ(p) = p-1 for prime p) to composite moduli.[1]
Carmichael's first main theorem (Theorem I) establishes the universal exponent property: for any positive integer n, x^{\lambda(n)} \equiv 1 \pmod{n} holds for every integer x coprime to n.[1] This theorem underscores λ(n) as the Carmichael function's core role in describing the maximal order of elements modulo n, with minimality inherent to the definition.
Carmichael also provides the explicit construction for λ(n) in terms of the prime power factorization of n: if n = 2^a p_1^{b_1} \cdots p_k^{b_k} where the p_i are distinct odd primes, then \lambda(n) = \operatorname{lcm}[\lambda(2^a), \lambda(p_1^{b_1}), \dots, \lambda(p_k^{b_k})], with \lambda(p^b) = \phi(p^b) = p^{b-1}(p-1) for odd prime p and b ≥ 1, \lambda(2^a) = \phi(2^a) = 2^{a-1} for a ≤ 2, and \lambda(2^a) = 2^{a-2} for a > 2.[1] This multiplicativity via the least common multiple ensures λ(n) captures the group's structure across prime factors. His second main theorem (Theorem II) establishes the existence of primitive λ-roots: in the congruence x^{\lambda(n)} \equiv 1 \pmod{n}, there exists a primitive λ-root g, with exactly φ(λ(n)) primitive roots congruent to powers of g.[1]
Carmichael's fourth main theorem (Theorem IV) addresses the preimages under λ: for a fixed positive integer a, if x_1 is the largest integer such that λ(x_1) = a, then every other x with λ(x) = a divides x_1, and the complete set of such x consists of the divisors d of x_1 for which λ(d) = a.[1] This result characterizes the solutions to λ(n) = k for given k, highlighting the function's selective growth and divisibility properties.
Proof for prime powers
The Carmichael function \lambda(n) is defined as the exponent of the multiplicative group (\mathbb{Z}/n\mathbb{Z})^*, the smallest positive integer m such that a^m \equiv 1 \pmod{n} for all a coprime to n. For n = p^k where p is prime and k \geq 1, explicit formulas for \lambda(p^k) follow from the structure of this group.[35]
Case of Odd Prime p
For an odd prime p and k \geq 1, the group (\mathbb{Z}/p^k \mathbb{Z})^* is cyclic of order \phi(p^k) = p^{k-1}(p-1), where \phi is Euler's totient function. The exponent of a cyclic group equals its order, so \lambda(p^k) = \phi(p^k) = p^{k-1}(p-1). A generator g of this group has order exactly p^{k-1}(p-1).[36]
To establish cyclicity, proceed by induction on k. For the base case k=1, (\mathbb{Z}/p\mathbb{Z})^* has order p-1 and is cyclic; this follows from Fermat's Little Theorem, which states that a^{p-1} \equiv 1 \pmod{p} for p \nmid a, so the order of any a divides p-1, and the existence of a primitive root (generator of order p-1) is a standard result obtained by counting elements of each possible order d \mid p-1 (there are exactly \phi(d) such elements) and showing the group order is fully accounted for by these cyclic subgroups.[37]
For k=2, let x be a generator modulo p (order p-1). The order of x modulo p^2 divides p(p-1). If it is p(p-1), then x generates (\mathbb{Z}/p^2 \mathbb{Z})^*. Otherwise, it is p-1, so x^{p-1} \equiv 1 \pmod{p^2}. Consider y = x + p; by the binomial theorem,
y^{p-1} = (x + p)^{p-1} \equiv x^{p-1} + (p-1) x^{p-2} \cdot p \pmod{p^2}.
Since x^{p-1} \equiv 1 \pmod{p^2} and p \nmid (p-1) x^{p-2} (as p is odd and x is a unit modulo p), the term (p-1) x^{p-2} p \not\equiv 0 \pmod{p^2}, so y^{p-1} \not\equiv 1 \pmod{p^2}. But y^{p(p-1)} = (y^{p-1})^p \equiv 1^p = 1 \pmod{p^2} by Euler's theorem, and no smaller positive exponent works (as orders divide p(p-1)), so y has order p(p-1) and generates (\mathbb{Z}/p^2 \mathbb{Z})^*.[36]
For the inductive step, assume (\mathbb{Z}/p^k \mathbb{Z})^* is cyclic for some k \geq 2, generated by z of order p^{k-1}(p-1). The order of z modulo p^{k+1} divides p^k (p-1). If it equals p^k (p-1), then z generates (\mathbb{Z}/p^{k+1} \mathbb{Z})^*. Suppose instead it is p^{k-1}(p-1), so z^{p^{k-1}(p-1)} \equiv 1 \pmod{p^{k+1}}. Let y = z^{p^{k-1}(p-1)}; then y \equiv 1 \pmod{p^k} by the induction hypothesis, but y^p = z^{p^k (p-1)} \equiv 1 \pmod{p^{k+1}} by Euler's theorem. A key lemma states that y^p \equiv 1 \pmod{p^{k+1}} if and only if y \equiv 1 \pmod{p^k}. Since the "if" direction holds trivially and the "only if" follows from the p-adic valuation v_p(y^p - 1) = v_p(y - 1) when v_p(y - 1) \geq 1 (as p odd), assuming y \not\equiv 1 \pmod{p^{k+1}} would contradict the minimality unless the order increases, but the assumption leads to y \equiv 1 \pmod{p^{k+1}}, implying the order of z modulo p^k divides a proper divisor, contradicting induction. Thus, the order modulo p^{k+1} is p^k (p-1), completing the induction.[36]
Case of p=2
For k=1, (\mathbb{Z}/2\mathbb{Z})^* = \{1\} is trivial, so \lambda(2) = 1. For k=2, (\mathbb{Z}/4\mathbb{Z})^* = \{1,3\} \cong C_2 (cyclic of order $2), so \lambda(4) = 2. For k \geq 3, (\mathbb{Z}/2^k \mathbb{Z})^* \cong C_2 \times C_{2^{k-2}}, where C_mdenotes the cyclic group of orderm; the exponent is \mathrm{lcm}(2, 2^{k-2}) = 2^{k-2}, so \lambda(2^k) = 2^{k-2}$.[8]
To prove the isomorphism, note that -1 has order $2(since(-1)^2 = 1and-1 \not\equiv 1 \pmod{2^k}). Next, $5 has order $2^{k-2}, proved by induction on k. For the base k=3, modulo $8: 5^1 = 5 \not\equiv 1, 5^2 = 25 \equiv 1 \pmod{8}, so order 2 = 2^{3-2}. Assume the order of $5 modulo $2^{k-1} (k-1 \geq 3) is $2^{k-3}. Modulo $2^k, the order divides \phi(2^k) = 2^{k-1} (by Euler's theorem) and is a multiple of $2^{k-3}, so it is $2^{k-3}, $2^{k-2}, or $2^{k-1}. It cannot be $2^{k-3}: $5^{2^{k-3}} \equiv 1 \pmod{2^{k-1}} by induction, so $5^{2^{k-3}} = 1 + t \cdot 2^{k-1} for some integer t; if \equiv 1 \pmod{2^k}, then $2^k \mid t \cdot 2^{k-1}, so $2 \mid t. But $5 = 1 + 4 = 1 + 2^2, and expanding (1 + 2^2)^{2^{k-3}} via the binomial theorem gives
(1 + 2^2)^{2^{k-3}} = 1 + \binom{2^{k-3}}{1} 2^2 + \sum_{i=2}^{2^{k-3}} \binom{2^{k-3}}{i} 2^{2i}.
The i=1 term is $2^{k-3} \cdot 2^2 = 2^{k-1}, and for i \geq 2, each term has 2-adic valuation at least k, so \equiv 0 \pmod{2^k}. Thus, (1 + 2^2)^{2^{k-3}} \equiv 1 + 2^{k-1} \pmod{2^k}, so t \equiv 1 \pmod{2} (odd), hence t not even and $5^{2^{k-3}} \not\equiv 1 \pmod{2^k}. The order cannot be $2^{k-1}, since the maximal order in the group is $2^{k-2} (as established by the structure). Thus, the order is $2^{k-2}.[38]
The elements -1 and $5generate(\mathbb{Z}/2^k \mathbb{Z})^, as the homomorphism f: \langle -1 \rangle \times \langle 5 \rangle \to (\mathbb{Z}/2^k \mathbb{Z})^sending(a,b) \mapsto a bis well-defined (orders preserved), surjective (spans all odd residues via explicit construction or counting:|\langle -1 \rangle \times \langle 5 \rangle| = 2 \cdot 2^{k-2} = \phi(2^k)), and thus an [isomorphism](/page/Isomorphism) by [Lagrange's theorem](/page/Lagrange's_theorem). The subgroups commute since -1is central. This confirms the structureC_2 \times C_{2^{k-2}}and the exponent2^{k-2}$.[8]
Extension to composite numbers
To extend the Carmichael function to a general positive integer n > 1 with prime factorization n = \prod p_i^{k_i} (distinct primes p_i, k_i \geq 1), the Chinese Remainder Theorem establishes that the multiplicative group of units (\mathbb{Z}/n\mathbb{Z})^\times is isomorphic to the direct product \prod (\mathbb{Z}/p_i^{k_i}\mathbb{Z})^\times.
The exponent of a finite direct product of abelian groups equals the least common multiple of the exponents of the factors. Therefore, \lambda(n) is the least common multiple of the \lambda(p_i^{k_i}).
For any integer a coprime to n, since \lambda(n) is a multiple of each \lambda(p_i^{k_i}), the prime power result implies a^{\lambda(n)} \equiv 1 \pmod{p_i^{k_i}} for every i. As the moduli p_i^{k_i} are pairwise coprime, the Chinese Remainder Theorem yields a^{\lambda(n)} \equiv 1 \pmod{n}.
This \lambda(n) is minimal because the isomorphism preserves orders: for each i, there exists an element in (\mathbb{Z}/p_i^{k_i}\mathbb{Z})^\times of order \lambda(p_i^{k_i}), corresponding to an element in (\mathbb{Z}/n\mathbb{Z})^\times whose order is exactly \lambda(p_i^{k_i}) (dividing any common exponent), so the overall exponent is at least the lcm, matching the upper bound.
The result for multiple prime factors follows directly from the product structure but can also be established by induction on the number of distinct primes r. The base case r=1 is the prime power result (including the special case for powers of 2). For the inductive step, factor n = m \cdot q^l with q prime not dividing m (r-1 primes in m); the Chinese Remainder Theorem gives the group isomorphism as above, so \lambda(n) = \operatorname{lcm}(\lambda(m), \lambda(q^l)), and induction applies to \lambda(m). The handling of 2 (whether as the sole prime or alongside odds) aligns with the prime power definition.