Carmichael function calculator

How it works

The Carmichael function $\lambda(n)$ is the smallest $m \ge 1$ such that $a^m \equiv 1 \pmod n$ for every $a$ coprime to $n$, the exponent of the group $\mathbb Z_n^*$. It always divides $\varphi(n)$ and equals the largest order of an element.

It follows from the factorization: $\lambda(p^e) = p^{e-1}(p - 1)$ for odd primes, $\lambda(2) = 1$, $\lambda(4) = 2$, $\lambda(2^e) = 2^{e-2}$ for $e \ge 3$, and for coprime parts $\lambda(mn) = \operatorname{lcm}(\lambda(m), \lambda(n))$. So $\lambda(n) = \varphi(n)$ exactly when primitive roots exist.

In RSA one may use $\lambda(N) = \operatorname{lcm}(p - 1, q - 1)$ instead of $\varphi(N)$ to compute the private exponent, giving a smaller $d$ (the FIPS 186 standard for RSA keys prescribes $\lambda$). A composite $n$ with $\lambda(n) \mid n - 1$ passes Fermat’s test for every base coprime to it: these are the Carmichael numbers, such as $561 = 3 \cdot 11 \cdot 17$ with $\lambda(561) = 80$.