Difference between revisions of "Carmichael function"

(First Definition)
m
 
(8 intermediate revisions by 3 users not shown)
Line 2: Line 2:
  
 
== First Definition ==
 
== First Definition ==
<math>\boxed{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.  
Line 8: Line 8:
  
  
Suppose </math>n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}<math>. We have
+
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}
+
<center><p><math>\lambda(n) = \begin{cases}
 
   \phi(n) &
 
   \phi(n) &
 
     \mathrm {for}\ n=p^{\alpha},\ \mathrm {with}\ p=2\ \mathrm {and}\ \alpha\le 2,\ \mathrm {or}\ p\ge 3\
 
     \mathrm {for}\ n=p^{\alpha},\ \mathrm {with}\ p=2\ \mathrm {and}\ \alpha\le 2,\ \mathrm {or}\ p\ge 3\
Line 17: Line 17:
 
   \mathrm{lcm} (\lambda(p_1^{\alpha_1}), \lambda(p_2^{\alpha_2}), \ldots, \lambda(p_k^{\alpha_k})) &
 
   \mathrm{lcm} (\lambda(p_1^{\alpha_1}), \lambda(p_2^{\alpha_2}), \ldots, \lambda(p_k^{\alpha_k})) &
 
     \mathrm{for}\ \mathrm{all}\ n.
 
     \mathrm{for}\ \mathrm{all}\ n.
\end{cases}<math></p></center>}</math>
+
\end{cases}</math></p></center>
  
=== Examples ===
+
== Examples ==
{{stub}}
 
  
 
Evaluate <math>2009^{2009}\pmod{1000}</math>.
 
Evaluate <math>2009^{2009}\pmod{1000}</math>.
Line 28: Line 27:
  
 
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>.
 
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 ===
 
{{stub}}
 
  
 
== See also ==
 
== See also ==
Line 37: Line 33:
 
* [[Modular arithmetic]]
 
* [[Modular arithmetic]]
 
* [[Euler's totient theorem]]
 
* [[Euler's totient theorem]]
 +
* [[Carmichael numbers]]
  
 
[[Category:Functions]]
 
[[Category:Functions]]
 
[[Category:Number theory]]
 
[[Category:Number theory]]
 +
 +
{{stub}}

Latest revision as of 10:56, 1 August 2022

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

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

See also

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