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

$$\lambda(n)=\cases{ \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

$$\lambda(1) = 1$$

$$\lambda(2) = 1$$

$$\lambda(4) = 2$$

$$\lambda(2^r) = 2^{r-2}$$

for $r\geq 3$, and

$$\lambda(p^r)=\phi(p^r)$$

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

References

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.'' http://www.research.att.com/~njas/sequences/eisonline.html 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.