6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Formatting advice: Instead of \mod, consider using \pmod. $\endgroup$ – Gregory Grant May 23 '15 at 12:37
  • $\begingroup$ 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. $\endgroup$ – user228113 May 23 '15 at 12:40
  • $\begingroup$ @G.Sassatelli Thanks by the way I took it from mathworld.wolfram.com/CarmichaelFunction.html $\endgroup$ – Jinn May 23 '15 at 12:43
  • $\begingroup$ See A note on Carmichael function $\endgroup$ – npatrat May 23 '15 at 12:53
  • $\begingroup$ It remains to determine $\lambda(p^m)$. Do you know the structure of the group $(\mathbb{Z}/p^m\mathbb{Z})^\times$? $\endgroup$ – Daniel Fischer May 23 '15 at 13:00
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

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