# Is every even number a value of the Carmichael function?

Except for the 1, all other values of the Carmichael function $\lambda$ are even. Does $\lambda$ take all even numbers? Is there an infinite family of even numbers that are not values of $\lambda$ ?

This question arose in the comments to What is the inverse of the Carmichael-function?.

-

The Carmichael function is defined recursively by the following formulas:

1. If $p_1,\ldots,p_n$ are distinct primes, then $$\lambda(p_1^{k_1} \cdots p_n^{k_n}) \;=\; \text{lcm}\bigl(\lambda(p_1^{k_1}),\ldots,\lambda(p_n^{k_n})\bigr)$$

2. If $p$ is an odd prime and $k\geq 1$, then $\lambda(p^k) = p^{k-1}(p-1)$.

3. $\lambda(2) = 1$, $\lambda(4) = 2$, and $\lambda(2^k) = 2^{k-2}$ for $k \geq 3$.

Since $\lambda(p^k)$ is even for any prime power $p^k$ other than $2$, the values Carmichael function are always even except for $\lambda(1) = \lambda(2) = 1$.

Moreover, if $p$ is an odd prime and $p \mid \lambda(n)$, then either:

1. $(p-1) \mid \lambda(n)$, or

2. $p \mid (q-1)$ and $(q-1) \mid \lambda(n)$ for some prime $q$.

This places severe restrictions on the values of the Carmichael function. In particular, if $p$ is an odd prime and $2p+1$ is not prime, then $2p$ is not a possible value of the Carmichael function. Thus, the numbers $\{14,26,34,38,\ldots\}$ do not arise as values of the Carmichael function.

Note that this list is not exhaustive. For example, $68$ is not a value of the Carmichael function, though it is not of the form I have indicated.

-
$14,26,34,38$ are also not values of Euler's $\phi$: oeis.org/A005277 . Is there a number that is taken by $\phi$ but not by $\lambda$? And conversely? (Perhaps this should be a separate question...) – lhf Jun 3 '11 at 19:16
See oeis.org/A002174 for the list of values taken by $\lambda$. Apparently 90 is a value for $\lambda$ but not for $\phi$, – Jim Belk Jun 3 '11 at 20:26
thanks a lot. – lhf Jun 3 '11 at 20:48

Also note that the list of even value not taken by $\lambda$ or $\phi$ is infinite. In fact, it can be shown that most even numbers are not in the image of either $\lambda$ or $\phi$.

-
For example, if m=2p, where p is a prime, yet 2p+1 is not a prime, then there is no solution to either \lambda(n)=m or \phi(n)=m. – Nick H. Jan 10 '12 at 23:02