I have been reading about the Carmichael function recently and I would like to ask about some elementary implication of its properties as I haven't found it stated explicitly.

If I understand it right: when the Carmichael function $\lambda$ for a number $p$ takes the value $\lambda(p)=p-1,$ then $p$ is a prime number. This also means that there must exist a primitive root of unity of that order: $\exists a: a^{p-1} \equiv 1 \pmod p.$

Is it then correct to say, that $p$ is a prime number if and only if $\mathbb{Z}/p\mathbb{Z}$ has a primitive root of unity of the order of $p-1$?

  • $\begingroup$ The Carmichael function is not really relevant. Let $n\gt 1$. Tf $a$ is relatively prime to $n$, then $a^{\varphi(n)}\equiv 1\pmod{n}$, where $\varphi$ is the Euler $\varphi$-function. If $n$ is not prime, then $\varphi(n)\lt n-1$, so $a$ cannot have order $n-1$. For the other direction, it is a standard (but not easy) theorem that any prime has a primitive root. $\endgroup$ – André Nicolas Mar 22 '15 at 14:01
  • $\begingroup$ You say that the Carmichael function is not really relevant, but it seems to be connected with the Euler $\varphi$-function. Anyway - could you tell me what is the name of that theorem you mentioned? Thanks for helping out! $\endgroup$ – glamredhel Mar 22 '15 at 14:17
  • $\begingroup$ It doesn't really have a standard name, the result is that every prime has a primitive root. The Carmichael function is indeed a close relative of the Euler $\varphi$-function, which I did use. $\endgroup$ – André Nicolas Mar 22 '15 at 15:29
  • $\begingroup$ I would say that $n\ge 2$ is prime if and only if $\mathbb{Z}_n$ has an element of order $n-1$. A number $a$ is a primitive root of $n$ if and only if $a$ has order $\varphi(n)$ modulo $n$. The numbers $n\ge 2$ that have primitive roots are $2$, $4$, any positive power $p^k$ of an odd prime $p$, and also $2p^k$. $\endgroup$ – André Nicolas Mar 22 '15 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.