Difference between revisions of "Carmichael function"

(First Definition)
m
 
(One intermediate revision by the same user not shown)
Line 2: Line 2:
  
 
== First Definition ==
 
== 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>.
+
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_(group theory)|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.  
 
This function is also known as the ''reduced totient function'' or the ''least universal exponent'' function.  

Latest revision as of 15:54, 26 February 2020

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]

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