Namespaces
Variants
Actions

Carmichael function

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 11A25 [MSN][ZBL]

of a positive integer $n$

The exponent of the multiplicative group of integers modulo $n$, denoted $\lambda(n)$; the least positive integer $\lambda$ such that $a^\lambda \equiv 1 \pmod n$ for all integers $a$ coprime to $n$. It is equal to the least common multiple of its values on the prime power factors of $n$: $$ \lambda(n) = \mathrm{lcm}\{\lambda(p_i^{a_i})\}\ \ \text{where}\ n = \prod_i p_i^{a_i} \ . $$

Since the multiplicative group modulo an odd prime power $p^a$ is cyclic, in these cases we have $\lambda(p^a) = \phi(p^a) = p^{a-1}(p-1)$ where $\phi$ denotes the Euler totient function. For powers of 2, we have $\lambda(2) = 1$, $\lambda(4)= 2$ and $\lambda(2^a) = 2^{a-2}$ for $a \ge 3$.

The order of the multiplicative group modulo $n$ is $\phi(n)$, so by Lagrange's theorem in group theory, $\lambda(n)$ divides $\phi(n)$.

A Carmichael number is a composite number with the property that $\lambda(n)$ divides $n-1$.

References

  • Eric Bach, Jeffrey O. Shallit, Algorithmic Number Theory: Efficient algorithms, Volume 1, MIT Press (1996) ISBN 0262024055
How to Cite This Entry:
Carmichael function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Carmichael_function&oldid=54695