TOPICS
Search

Carmichael Function


There are two definitions of the Carmichael function. One is the reduced totient function (also called the least universal exponent function), defined as the smallest integer lambda(n) such that k^(lambda(n))=1 (mod n) for all k relatively prime to n. The multiplicative order of a (mod n) is at most lambda(n) (Ribenboim 1989). The first few values of this function, implemented as CarmichaelLambda[n], are 1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 10, ... (OEIS A002322).

It is given by the formula

 lambda(n)=LCM[(p_i-1)p_i^(alpha_i-1)]_i,
(1)

where p_i^(alpha_i) are primaries.

It can be defined recursively as

 lambda(n)={phi(n)   for n=p^alpha, with p=2 and alpha<=2, or p>=3; 1/2phi(n)   for n=2^alpha and alpha>=3; LCM[lambda(p_i^(alpha_i))]_i   for n=product_(i)p_i^(alpha_i).
(2)

Some special values include

 lambda(2^n)={1   for n=1, n=2; 2   for n=2; 2^(n-2)   otheriwse
(3)

and

 lambda(n!)={1   for n=1, n=2; 2   for n=3; 4   for n=5; (n!)/(2n#)   otherwise,
(4)

where n# is a primorial (S. M. Ruiz, pers. comm., Jul. 5, 2009).

The second Carmichael's function lambda^'(n) is given by the least common multiple (LCM) of all the factors of the totient function phi(n), except that if 8|n, then 2^(alpha-2) is a factor instead of 2^(alpha-1). The values of lambda^'(n) for the first few n are 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 2, 12, ... (OEIS A011773).

This function has the special value

 lambda^'(p^r)=phi(p^r)
(5)

for p an odd prime and r>=1.


See also

Modulo Multiplication Group, Totient Function

Related Wolfram sites

http://functions.wolfram.com/NumberTheoryFunctions/CarmichaelLambda/

Explore with Wolfram|Alpha

References

Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, p. 27, 1989.Riesel, H. "Carmichael's Function." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 273-275, 1994.Sloane, N. J. A. Sequences A002322/M0298 and A011773 in "The On-Line Encyclopedia of Integer Sequences."Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, p. 226, 1991.

Referenced on Wolfram|Alpha

Carmichael Function

Cite this as:

Weisstein, Eric W. "Carmichael Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CarmichaelFunction.html

Subject classifications