Difference between revisions of "Carmichael function"

(Examples)
(Examples)
Line 25: Line 25:
 
[http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1363764#1363764]
 
[http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1363764#1363764]
  
<math>\phi{1000}</math>
+
<math>{\alpha{\boxed{\lambda{\boxed{\phi{(1000)}}}}}}</math>
  
 
== Second Definition ==
 
== Second Definition ==

Revision as of 00:43, 10 August 2019

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

First Definition

The Carmichael function $\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 integers $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 $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

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

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

${\alpha{\boxed{\lambda{\boxed{\phi{(1000)}}}}}}$

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