Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
$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
1  
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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.