6
$\begingroup$

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?.

2 Answers 2

8

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.

  • 2
    See http://oeis.org/A002174 for the list of values taken by $\lambda$. Apparently 90 is a value for $\lambda$ but not for $\phi$,2011-06-03
2

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$.

  • 0
    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.2012-01-10