info prev up next book cdrom email home

Carmichael Function

$\lambda(n)$ is the smallest integer such that $k^n\equiv 1\ \left({{\rm mod\ } {n}}\right)$ for all $k$ Relatively Prime to $n$. It can be defined recursively by

\phi(n) & for $n=p^\alpha, p=2 {\rm\ and...
...a({p_i}^{\alpha_i})]_i & for $n=\prod_i {p_i}^{\alpha_i}$.\cr}

Some special values are
$\displaystyle \lambda(1)$ $\textstyle =$ $\displaystyle 1$  
$\displaystyle \lambda(2)$ $\textstyle =$ $\displaystyle 1$  
$\displaystyle \lambda(4)$ $\textstyle =$ $\displaystyle 2$  
$\displaystyle \lambda(2^r)$ $\textstyle =$ $\displaystyle 2^{r-2}$  

for $r\geq 3$, and


for $p$ an Odd Prime and $r\geq 1$. The Order of $a$ (mod $n$) is at most $\lambda(n)$ (Ribenboim 1989). The values of $\lambda(n)$ for the first few $n$ are 1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 10, 2, 12, ... (Sloane's A002322).

See also Modulo Multiplication Group


Ribenboim, P. The Book of Prime Number Records, 2nd ed. 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. Sequence A002322/M0298 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, p. 226, 1991.

© 1996-9 Eric W. Weisstein