Difference between revisions of "Carmichael function"
(→Examples) |
(→First Definition) |
||
| Line 2: | Line 2: | ||
== First Definition == | == First Definition == | ||
| − | The Carmichael function <math>\lambda< | + | <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}< | + | 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}< | + | \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 
.
First Definition
$\boxed{The Carmichael function$ (Error compiling LaTeX. Unknown error_msg)\lambda
n![$to be the smallest [[positive integer]]$](http://latex.artofproblemsolving.com/9/c/1/9c1b27a5a173e7a39e287dbd8a7c336816d6994d.png)
\lambda(n)
a^{\lambda(n)} \equiv 1\pmod {n}![$for all positive [[integer]]s$](http://latex.artofproblemsolving.com/3/8/3/383c6461856f52b00e4df6ece0510c40e113c2d9.png)
a![$[[relatively prime]] to$](http://latex.artofproblemsolving.com/b/3/8/b38fa41ce7a0cfaa318ee56fd2f0379be8cc18bb.png)
n![$. The [[order]] of$](http://latex.artofproblemsolving.com/4/1/6/416168f50c14bd52258d80befeb5909e206fb575.png)
a\pmod {n}
\lambda(n)$.
This function is also known as the ''reduced totient function'' or the ''least universal exponent'' function.
Suppose$ (Error compiling LaTeX. Unknown error_msg)n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. We have
<center><p>$ (Error compiling LaTeX. Unknown error_msg)\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. Unknown error_msg)
Examples
This article is a stub. Help us out by expanding it.
Evaluate 
.
[1]
Second Definition
The second definition of the Carmichael function is the least common multiples of all the factors of 
. It is written as 
. However, in the case 
, we take 
as a factor instead of 
.
Examples
This article is a stub. Help us out by expanding it.
