Carmichael function

Revision as of 19:53, 26 January 2007 by Chess64 (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

There are two different functions that are both called Carmichael function. It is similar to the totient function

The first definition

The first definition is also called the reduced totient function or the least universal exponent function. It is defined as the smallest positive integer $\lambda(n)$ such that $a^{\lambda(n)} \equiv 1\pmod {n}$ for all positive integers $a$ relatively prime to $n$. The modulo order of $a\pmod {n}$ is less than or equal to $\lambda(n)$.

Suppose $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. We have

$\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}$

Examples

The second definition

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

Examples

See also