- for every integer a between 1 and n that is coprime to n.
The Carmichael function is named after the American mathematician Robert Carmichael and is also known as the reduced totient function or the least universal exponent function.
- 1 Numerical example
- 2 Computing with Carmichael's theorem
- 3 Properties of the Carmichael function
- 4 See also
- 5 Notes
- 6 References
Carmichael's function at 8 is 2, i.e. , because for any number a co-prime to 8 it holds that a2 ≡ 1 (mod 8). Namely, 12 = 1 (mod 8), 32 = 9 ≡ 1 (mod 8), 52 = 25 ≡ 1 (mod 8) and 72 = 49 ≡ 1 (mod 8). Euler's totient function is 4 at 8, i.e. , because there are 4 numbers lesser than and coprime to 8 (1, 3, 5, and 7). Euler's theorem assures that a4 ≡ 1 (mod 8) for all a coprime to 8, but 4 is not the smallest such exponent.
Computing with Carmichael's theorem
By the fundamental theorem of arithmetic any n > 1 can be written in a unique way as
This can be proved using the Chinese Remainder Theorem.
Carmichael's theorem explains how to compute λ of a prime power: for a 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 half of the Euler totient.
Euler's function for prime powers is given by
Properties of the Carmichael function
λ(n) divides φ(n)
This follows from elementary group theory, because the exponent of any finite abelian group must divide the order of the group. λ(n) is the exponent of the multiplicative group of integers modulo n while φ(n) is the order of that group.
We can thus view Carmichael's theorem as a sharpening of Euler's theorem.
Suppose for all numbers a coprime with n. Then .
Proof. If with , then for all numbers a coprime with n. It follows , since and the minimal positive such number.
Proof. The result follows from the formula
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
If has maximum prime exponent 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:
Where B is a constant,
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 .
Image of the function
The set of values of the Carmichael function has counting function
- 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
- Ford, Kevin; Luca, Florian; Pomerance, Carl (27 August 2014). "The image of Carmichael's λ-function". Algebra & Number Theory. 8: 2009–2026. arXiv: [math.NT]. doi:10.2140/ant.2014.8.2009.
- Erdős, Paul; Pomerance, Carl; Schmutz, Eric (1991). "Carmichael's lambda function". Acta Arithmetica. 58: 363–385. doi:10.4064/aa-58-4-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. doi:10.1090/s0025-5718-00-01282-5. ISSN 0025-5718. MR 1836921. Zbl 1029.11043.
- Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 32–36,193–195. ISBN 1-4020-2546-7. Zbl 1079.11001.
- Carmichael, R. D. The Theory of Numbers. Nabu Press. ISBN 1144400341.