Difference between revisions of "Carmichael function"
(→Examples) |
|||
| Line 21: | Line 21: | ||
=== Examples === | === Examples === | ||
{{incomplete|section}} | {{incomplete|section}} | ||
| + | |||
| + | Evaluate <math>2009^{2009}</math> (mod <math>1000</math>). | ||
| + | [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1363764#1363764] | ||
== Second Definition == | == Second Definition == | ||
Revision as of 21:33, 3 January 2009
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 
(mod 
).
[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 
.
