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

Difference between revisions of "Carmichael function"

(→‎First Definition)
m
 
(8 intermediate revisions by 3 users not shown)
Line 2: Line 2:
  
 
== First Definition ==
 
== First Definition ==
−
<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>.
+
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 8: Line 8:
  
  
−
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
  
−
<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}<math></p></center>}</math>
+
\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"