View source for Carmichael function

There are two different [[function]]s that are both called '''Carmichael function'''.  Both are similar to [[Euler's totient function]] <math>\phi</math>.

== First Definition ==
The Carmichael function <math>\lambda</math> is defined at <math>n</math> to be the smallest [[positive integer]] <math>\lambda(n)</math> such that <math>a^{\lambda(n)} \equiv 1\pmod {n}</math> for all positive [[integer]]s <math>a</math> [[relatively prime]] to <math>n</math>. The [[order]] of <math>a\pmod {n}</math> always divides <math>\lambda(n)</math>.

This function is also known as the ''reduced totient function'' or the ''least universal exponent'' function. 



Suppose <math>n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}</math>. We have

<center><p><math>\lambda(n) = \begin{cases}
  \phi(n) &
    \mathrm {for}\ n=p^{\alpha},\ \mathrm {with}\ p=2\ \mathrm {and}\ \alpha\le 2,\ \mathrm {or}\ p\ge 3\\
  \frac{1}{2}\phi(n) &
    \mathrm {for}\ n=2^{\alpha}\ \mathrm {and}\ \alpha\ge 3\\
  \mathrm{lcm} (\lambda(p_1^{\alpha_1}), \lambda(p_2^{\alpha_2}), \ldots, \lambda(p_k^{\alpha_k})) &
     \mathrm{for}\ \mathrm{all}\ n.
\end{cases}</math></p></center>

=== Examples ===
{{incomplete|section}}

== Second Definition ==

The second definition of the Carmichael function is the least common multiples of all the factors of <math>\phi(n)</math>. It is written as <math>\lambda'(n)</math>. However, in the case <math>8|n</math>, we take <math>2^{\alpha-2}</math> as a factor instead of <math>2^{\alpha-1}</math>.

=== Examples ===
{{incomplete|section}}

== See also ==

* [[Number theory]]
* [[Modular arithmetic]]
* [[Euler's totient theorem]]

[[Category:Functions]]
[[Category:Number theory]]