for every integer a that is coprime to n. In other words, in more algebraic terms, it defines the exponent of the multiplicative group of integers modulo n. The Carmichael function is also known as the reduced totient function or the least universal exponent function, and is sometimes also denoted .
72 = 49 ≡ 1 (mod 8) because 7 and 8 are coprime (their greatest common divisor equals 1; they have no common factors) and the value of Carmichael's function at 8 is 2. Euler's totient function is 4 at 8 because there are 4 numbers lesser than and coprime to 8 (1, 3, 5, and 7). Whilst it is true that 74 = 2401 ≡ 1 (mod 8), as shown by Euler's theorem, raising 7 to the fourth power is unnecessary because the Carmichael function indicates that 7 squared equals 1 (mod 8). Raising 7 to exponents greater than 2 only repeats the cycle 7, 1, 7, 1, ....
For a power of an odd prime, twice the power of an odd prime, and for 2 and 4, λ(n) is equal to the Euler totient φ(n); for powers of 2 greater than 4 it is equal to one half of the Euler totient:
Euler's function for prime powers is given by
By the fundamental theorem of arithmetic any n > 1 can be written in a unique way
where p1 < p2 < ... < pω are primes and the ai > 0. (n = 1 corresponds to the empty product.)
For general n, λ(n) is the least common multiple of λ of each of its prime power factors:
Carmichael's theorem states that if a is coprime to n, then
where is the Carmichael function defined above. In other words, it asserts the correctness of the formulas. This can be proven by considering any primitive root modulo n and the Chinese remainder theorem.
Hierarchy of results
Since λ(n) divides φ(n), Euler's totient function, the Carmichael function is a stronger result than the classical Euler's theorem. Clearly Carmichael's theorem is related to Euler's theorem, because the exponent of a finite abelian group must divide the order of the group, by elementary group theory. The two functions differ already in small cases: λ(15) = 4 while φ(15) = 8 (see A033949 for the associated n).
Fermat's little theorem is the special case of Euler's theorem in which n is a prime number p. Carmichael's theorem for a prime p gives the same result, because the group in question is a cyclic group for which the order and exponent are both p − 1.
Properties of the Carmichael function
For all positive integers and it holds
This is an immediate consequence of the recursive definition of the Carmichael function.
Primitive m-th roots of unity
Let and be coprime and let be the smallest exponent with , then it holds
That is, the orders of primitive roots of unity in the ring of integers modulo are divisors of .
Exponential cycle length
For a number with maximum prime exponent of under prime factorization, then for all (including those not co-prime to ) and all ,
In particular, for squarefree (), for all
Average and typical value
For any x > 16, and a constant B:
For all numbers N and all except o(N) positive integers n ≤ N:
For any sufficiently large number N and for any , there are at most
positive integers such that .
For any sequence of positive integers, any constant , and any sufficiently large i:
For a constant c and any sufficiently large positive A, there exists an integer such that . Moreover, n is of the form
for some square-free integer .
- Theorem 3 in Erdös (1991)
- Sándor & Crstici (2004) p.194
- Theorem 2 in Erdös (1991)
- Theorem 5 in Friedlander (2001)
- Theorem 1 in Erdös 1991
- Sándor & Crstici (2004) p.193
- Theorem 1 in Erdös 1991
- Erdős, Paul; Pomerance, Carl; Schmutz, Eric (1991). "Carmichael's lambda function". Acta Arithmetica 58: 363–385. ISSN 0065-1036. MR 1121092. Zbl 0734.11047.
- Friedlander, John B.; Pomerance, Carl; Shparlinski, Igor E. (2001). "Period of the power generator and small values of the Carmichael function". Mathematics of Computation 70 (236): 1591–1605,1803–1806. ISSN 0025-5718. MR 1836921. Zbl 1029.11043.
- Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 193–195. ISBN 1-4020-2546-7. Zbl 1079.11001.