Carmichael function

Revision as of 00:44, 10 August 2019 by Jatsing (talk | contribs) (First Definition)

There are two different functions called the Carmichael function. Both are similar to Euler's totient function $\phi$.

First Definition

$\boxed{The Carmichael function$ (Error compiling LaTeX. ! File ended while scanning use of \boxed.)\lambda$is defined at$n$to be the smallest [[positive integer]]$\lambda(n)$such that$a^{\lambda(n)} \equiv 1\pmod {n}$for all positive [[integer]]s$a$[[relatively prime]] to$n$. The [[order]] of$a\pmod {n}$always divides$\lambda(n)$.

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


Suppose$ (Error compiling LaTeX. ! Missing $ inserted.)n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. We have

<center><p>$ (Error compiling LaTeX. ! Missing $ inserted.)\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}$</p></center>}$ (Error compiling LaTeX. ! Extra }, or forgotten $.)

Examples

This article is a stub. Help us out by expanding it.

Evaluate $2009^{2009}\pmod{1000}$. [1]

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

This article is a stub. Help us out by expanding it.

See also

Invalid username
Login to AoPS