Difference between revisions of "Carmichael function"

(Examples)
(First Definition)
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>.
+
<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>.
  
 
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>
+
\end{cases}<math></p></center>}</math>
  
 
=== Examples ===
 
=== Examples ===

Revision as of 00:44, 10 August 2019

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