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"

 
m
 
(19 intermediate revisions by 9 users not shown)
Line 1: Line 1:
−
There are two different functions that are both called '''Carmichael function'''. It is similar to the [[totient function]]
+
There are two different [[function]]s called the '''Carmichael function'''. Both are similar to [[Euler's totient function]] <math>\phi</math>.
 +
 
 +
== 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_(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.
  
−
== The first definition ==
 
  
−
The first definition is also called the reduced totient function or the least universal exponent function. It is defined as the smallest positive integer <math>\lambda(n)</math> such that <math>a^{\lambda(n)} \equiv 1\pmod {n}</math> for all positive integers <math>a</math> relatively prime to <math>n</math>. The [[modulo order]] of <math>a\pmod {n}</math> is less than or equal to <math>\lambda(n)</math>.
 
  
 
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 16: Line 19:
 
\end{cases}</math></p></center>
 
\end{cases}</math></p></center>
  
−
=== Examples ===
+
== Examples ==
 +
 
 +
Evaluate <math>2009^{2009}\pmod{1000}</math>.
 +
[http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1363764#1363764]
  
−
== The second definition ==
+
== Second Definition ==
  
 
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 ===
 
  
 
== See also ==
 
== See also ==
Line 28: Line 32:
 
* [[Number theory]]
 
* [[Number theory]]
 
* [[Modular arithmetic]]
 
* [[Modular arithmetic]]
−
* [[Modulo order]]
 
−
* [[Totient function]]
 
 
* [[Euler's totient theorem]]
 
* [[Euler's totient theorem]]
 +
* [[Carmichael numbers]]
 +
 +
[[Category:Functions]]
 +
[[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"