Difference between revisions of "Carmichael function"
(→Examples) |
Enderramsby (talk | contribs) m |
||
(9 intermediate revisions by 3 users 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. | ||
Line 19: | Line 19: | ||
\end{cases}</math></p></center> | \end{cases}</math></p></center> | ||
− | + | == Examples == | |
− | |||
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>. | ||
− | |||
− | |||
− | |||
== 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 11:56, 1 August 2022
There are two different functions called the Carmichael function. Both are similar to Euler's totient function .
First Definition
The Carmichael function is defined at
to be the smallest positive integer
such that
for all positive integers
relatively prime to
. The order of
always divides
.
This function is also known as the reduced totient function or the least universal exponent function.
Suppose . We have
Examples
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
.
See also
This article is a stub. Help us out by expanding it.