# How can I prove the Carmichael theorem

I am trying to prove that these two definitions of Carmichael function are equivalent.

I am using this definition of Carmichael function:

$\lambda(n)$ is the smallest integer such that $k^{\lambda(n)}\equiv1 \pmod n\,$ $\forall k$ such that $\gcd(k,n)=1$.

to prove this one:

$\lambda(n) = \begin{cases}\phi(p^a) & (p=2\text{ and }a\le 2)\text{ or }(p\ge 3)\\\dfrac 1 2 \phi{(2^a)} & a\ge 3\\ \text{lcm}\left((\lambda(p_1^{a_1}),\cdots,\lambda(p_k^{a_k})\right)& \text{for }n=\prod_{i=1}^k p_i^{a_i} \end{cases}$

Since $a^{\lambda(n)}\equiv 1 \pmod n$, and $a^{\lambda(m)}\equiv1 \pmod m$ with $\gcd(m,n)=1 \implies a^{\text{lcm}({\lambda(n)},\lambda(m)}\equiv1 \pmod {nm}$

Hence $\lambda (mn)=\text{lcm}(\lambda(n), \lambda(n))$ for $m$ and $n$ coprime to each other.

How can I prove the other relations?

• Formatting advice: Instead of \mod, consider using \pmod. – Gregory Grant May 23 '15 at 12:37
• Also: formatted something. I failed to understand the meaning of the last case in the definition of $\lambda(n)$, therefore I left it as it was. For help. – user228113 May 23 '15 at 12:40
• @G.Sassatelli Thanks by the way I took it from mathworld.wolfram.com/CarmichaelFunction.html – Jinn May 23 '15 at 12:43
• – npatrat May 23 '15 at 12:53
• It remains to determine $\lambda(p^m)$. Do you know the structure of the group $(\mathbb{Z}/p^m\mathbb{Z})^\times$? – Daniel Fischer May 23 '15 at 13:00

You need to prove that there are primitive roots $\bmod p^k$ when $p$ is an odd prime. We can do this by induction over $k$

To do this prove the base case using the fact that multiplicative groups of finite fields are cyclic and using $\mathbb Z_p$ is a field.

After this prove it for $k=2$. Take $a$ a primitive root $\bmod p$, the order of the subgroup generated by $a$ of $\mathbb Z_{p^2}$ is either $p-1$ or $p(p-1)$ by Lagrange's theorem and the fact it is a multiple of $p-1$ since it is a primitive root $\bmod p$.

If it is not a primitive root $\bmod p^2$ then we have $a^{p-1}\equiv 1 \bmod p^2$

We now prove $a+p$ is a primitive root $\bmod p^2$. This is because $(a+p)^{p-1}=a^{p-1}+(p-1)a^{p-2}p+\binom{p-1}{2}a^{p-3}p^2+\dots +p^{p-1}\equiv a^ {p-1}+(p-1)a^{p-2}p\equiv 1+(p-1)a^{p-2}p\bmod p^2$

Since $(p-1)a^{p-2}p$ is not a multiple of $p^2$ we have that $1+(p-1)a^{p-2}p$ is not $1\bmod p^2$.

Hence the order of $a+p$ is not $p-1$ and since $a+p$ is also a primitive root $\bmod p$ we conclude it is a primitive root $\bmod p^2$.

We now use the lifting the exponent lemma to prove that a primitive root $\bmod p^2$ is a primitive root $\bmod p^k$ for any $k$.

Proof: Let $a$ be a primitive root $\bmod p^2$, to prove $a$ is a primitive root $\bmod p^k$ we have to prove $a^{p^{k-2}(p-1)}\not\equiv 1\bmod p^k$. In other words we must prove that $a^{p^{k-2}(p-1)}-1$ is not a multiple of $p ^k$.

We rewrite this as $a^{p^{k-2}(p-1)}-(1)^{p^{k-2}(p-1)}$ and we apply the lifting the exponent lemma to obtain that the maximum power of $p$ dividing $a^{p^{k-2}(p-1)}-(1)^{p^{k-2}(p-1)}$ is equal to the maximum power of $p$ dividing $a^{p-1}-1^{p-1}$ plus the maximum power of $p$ dividing $p^{k-2}$ in other words $k-2+1=k-1$. So $p^k$ does not divide $a^{p^{k-2}(p-1)}-1$ as desired.

This proves to us that $p^k$ has primitive roots for all powers of odd primes. In other words this proves $\lambda (p^k)=(p-1)p^{k-1}$ (Because there are $(p-1)p^k$ residue classes that are relatively prime to $p$ and we have proven that there is an element that reaches them all with its powers.

Proving $\lambda(2)=1$ and $\lambda (4)=2$ is easy by inspection. To prove $\lambda(2^k)=2^{k-2}$ can also be done using ideas similar to the previous ones.

Sketch of the proof:

Look at the problem $\bmod 8$. the residue classes are $1,3,5,7$ but the powers of any of these congruence classes, $a$ are always $1$ and $a\bmod 8$. This means that an element can generate at mos half of the residue classes (this is because it can only reach at most two of the four classes $\bmod 8$). Prove that the element $3$ does in fact have order $2^{n-2}$ and you are done.