Difference between revisions of "Carmichael function"
| Line 1: | Line 1: | ||
| − | There are two different | + | There are two different [[function]]s that are both called '''Carmichael function'''. Both are similar to [[Euler's totient function]] <math>\phi</math>. |
== The first definition == | == The 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>. | ||
| + | |||
| + | This function is also known as the ''reduced totient function'' or the ''least universal exponent'' function. | ||
| + | |||
| − | |||
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 | ||
| Line 28: | Line 31: | ||
* [[Number theory]] | * [[Number theory]] | ||
* [[Modular arithmetic]] | * [[Modular arithmetic]] | ||
| − | |||
| − | |||
* [[Euler's totient theorem]] | * [[Euler's totient theorem]] | ||
Revision as of 11:18, 29 January 2007
There are two different functions that are both called Carmichael function. Both are similar to Euler's totient function 
.
The 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
The 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 
.
