Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus
During AMC testing, the AoPS Wiki is in read-only mode and no edits can be made.

Difference between revisions of "Carmichael function"

m
m
 
(5 intermediate revisions by the same user not shown)
Line 19: Line 19:
 
\end{cases}</math></p></center>
 
\end{cases}</math></p></center>
  
−
=== Examples ===
+
== Examples ==
−
{{stub}}
 
  
 
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>.
−
 
−
=== Examples ===
 
−
{{stub}}
 
  
 
== 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 10:56, 1 August 2022

There are two different functions called the Carmichael function. Both are similar to Euler's totient function $\phi$.

First Definition

The Carmichael function $\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 integers $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 $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. We have

$\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}$

Examples

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}$.

See also

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Carmichael_function&oldid=176505"