Carmichael function#Carmichael's theorems

• {{math | n {{=}} 5}}. The set of numbers less than and coprime to 5 is {{math | {1,2,3,4}}}. Hence Euler's totient function has value {{math | φ(5) {{=}} 4}} and the value of Carmichael's function, {{math | λ(5)}}, must be a divisor of 4. The divisor 1 does not satisfy the definition of Carmichael's function since $a^1\; \backslash not\backslash equiv\; 1\backslash pmod\{5\}$ except for $a\backslash equiv1\backslash pmod\{5\}$. Neither does 2 since $2^2\; \backslash equiv\; 3^2\; \backslash equiv\; 4\; \backslash not\backslash equiv\; 1\backslash pmod\{5\}$. Hence {{math | λ(5) {{=}} 4}}. Indeed, $1^4\backslash equiv\; 2^4\backslash equiv\; 3^4\backslash equiv\; 4^4\backslash equiv1\backslash pmod\{5\}$. Both 2 and 3 are primitive {{mvar | λ}}-roots modulo 5 and also primitive roots modulo 5.
• {{math | n {{=}} 8}}. The set of numbers less than and coprime to 8 is {{math | {1,3,5,7} }}. Hence {{math | φ(8) {{=}} 4}} and {{math | λ(8)}} must be a divisor of 4. In fact {{math | λ(8) {{=}} 2}} since $1^2\backslash equiv\; 3^2\backslash equiv\; 5^2\backslash equiv\; 7^2\backslash equiv1\backslash pmod\{8\}$. The primitive {{mvar | λ}}-roots modulo 8 are 3, 5, and 7. There are no primitive roots modulo 8.

The Carmichael lambda function of a prime power can be expressed in terms of the Euler totient. Any number that is not 1 or a prime power can be written uniquely as the product of distinct prime powers, in which case {{mvar | λ}} of the product is the least common multiple of the {{mvar | λ}} of the prime power factors. Specifically, {{math | λ(n)}} is given by the recurrence

:$\backslash lambda(n)\; =\; \backslash begin\{cases\}$

\varphi(n) & \text{if }n\text{ is 1, 2, 4, or an odd prime power,}\\

\tfrac12\varphi(n) & \text{if }n=2^r,\ r\ge3,\\

\operatorname{lcm}\Bigl(\lambda(n_1),\lambda(n_2),\ldots,\lambda(n_k)\Bigr) & \text{if }n=n_1n_2\ldots n_k\text{ where }n_1,n_2,\ldots,n_k\text{ are powers of distinct primes.}

\end{cases}

Euler's totient for a prime power, that is, a number {{math | p^r}} with {{math | p}} prime and {{math | r ≥ 1}}, is given by

:$\backslash varphi(p^r)\; \{\{=\}\}\; p^\{r-1\}(p-1).$

{{anchor|Carmichael's theorem}}

Carmichael proved two theorems that, together, establish that if {{math | λ(n)}} is considered as defined by the recurrence of the previous section, then it satisfies the property stated in the introduction, namely that it is the smallest positive integer {{mvar | m}} such that $a^m\backslash equiv\; 1\backslash pmod\{n\}$ for all {{mvar | a}} relatively prime to {{mvar | n}}.

{{Math theorem |name=Theorem 1|math_statement=If {{mvar | a}} is relatively prime to {{mvar | n}} then $a^\{\backslash lambda(n)\}\backslash equiv\; 1\backslash pmod\{n\}$.Carmichael (1914) p.40}}

This implies that the order of every element of the multiplicative group of integers modulo {{mvar | n}} divides {{math | λ(n)}}. Carmichael calls an element {{mvar | a}} for which $a^\{\backslash lambda(n)\}$ is the least power of {{mvar | a}} congruent to 1 (mod {{mvar | n}}) a primitive λ-root modulo n.Carmichael (1914) p.54 (This is not to be confused with a primitive root modulo n, which Carmichael sometimes refers to as a primitive $\backslash varphi$-root modulo {{mvar | n}}.)

{{Math theorem |name=Theorem 2|math_statement=For every positive integer {{mvar | n}} there exists a primitive {{mvar | λ}}-root modulo {{mvar | n}}. Moreover, if {{mvar | g}} is such a root, then there are $\backslash varphi(\backslash lambda(n))$ primitive {{mvar | λ}}-roots that are congruent to powers of {{mvar | g}}.Carmichael (1914) p.55}}

If {{mvar | g}} is one of the primitive {{mvar | λ}}-roots guaranteed by the theorem, then $g^m\backslash equiv1\backslash pmod\{n\}$ has no positive integer solutions {{mvar | m}} less than {{math | λ(n)}}, showing that there is no positive {{math | m < λ(n)}} such that $a^m\backslash equiv\; 1\backslash pmod\{n\}$ for all {{mvar | a}} relatively prime to {{mvar | n}}.

The second statement of Theorem 2 does not imply that all primitive {{mvar | λ}}-roots modulo {{mvar | n}} are congruent to powers of a single root {{mvar | g}}.Carmichael (1914) p.56 For example, if {{math | n {{=}} 15}}, then {{math | λ(n) {{=}} 4}} while $\backslash varphi(n)=8$ and $\backslash varphi(\backslash lambda(n))=2$. There are four primitive {{mvar | λ}}-roots modulo 15, namely 2, 7, 8, and 13 as $1\backslash equiv2^4\backslash equiv8^4\backslash equiv7^4\backslash equiv13^4$. The roots 2 and 8 are congruent to powers of each other and the roots 7 and 13 are congruent to powers of each other, but neither 7 nor 13 is congruent to a power of 2 or 8 and vice versa. The other four elements of the multiplicative group modulo 15, namely 1, 4 (which satisfies $4\backslash equiv2^2\backslash equiv8^2\backslash equiv7^2\backslash equiv13^2$), 11, and 14, are not primitive {{mvar | λ}}-roots modulo 15.

For a contrasting example, if {{math | n {{=}} 9}}, then $\backslash lambda(n)=\backslash varphi(n)=6$ and $\backslash varphi(\backslash lambda(n))=2$. There are two primitive {{mvar | λ}}-roots modulo 9, namely 2 and 5, each of which is congruent to the fifth power of the other. They are also both primitive $\backslash varphi$-roots modulo 9.

In this section, an integer $n$ is divisible by a nonzero integer $m$ if there exists an integer $k$ such that $n\; =\; km$. This is written as

:$m\; \backslash mid\; n.$

Suppose {{math | a^m ≡ 1 (mod n)}} for all numbers {{mvar | a}} coprime with {{mvar | n}}. Then {{math | λ(n) {{!}} m}}.

Proof: If {{math | m {{=}} kλ(n) + r}} with {{math | 0 ≤ r < λ(n)}}, then

:$a^r\; =\; 1^k\; \backslash cdot\; a^r\; \backslash equiv\; \backslash left(a^\{\backslash lambda(n)\}\backslash right)^k\backslash cdot\; a^r\; =\; a^\{k\backslash lambda(n)+r\}\; =\; a^m\; \backslash equiv\; 1\backslash pmod\{n\}$

for all numbers {{mvar | a}} coprime with {{mvar | n}}. It follows that {{math | 1=r = 0}} since {{math | r < λ(n)}} and {{math | λ(n)}} is the minimal positive exponent for which the congruence holds for all {{mvar | a}} coprime with {{mvar | n}}.

This follows from elementary group theory, because the exponent of any finite group must divide the order of the group. {{math | λ(n)}} is the exponent of the multiplicative group of integers modulo {{mvar | n}} while {{math | φ(n)}} is the order of that group. In particular, the two must be equal in the cases where the multiplicative group is cyclic due to the existence of a primitive root, which is the case for odd prime powers.

We can thus view Carmichael's theorem as a sharpening of Euler's theorem.

:$a\backslash ,|\backslash ,b\; \backslash Rightarrow\; \backslash lambda(a)\backslash ,|\backslash ,\backslash lambda(b)$

Proof.

By definition, for any integer $k$ with $\backslash gcd(k,b)\; =\; 1$ (and thus also $\backslash gcd(k,a)\; =\; 1$), we have that $b\; \backslash ,|\backslash ,\; (k^\{\backslash lambda(b)\}\; -\; 1)$ , and therefore $a\; \backslash ,|\backslash ,\; (k^\{\backslash lambda(b)\}\; -\; 1)$. This establishes that $k^\{\backslash lambda(b)\}\backslash equiv1\backslash pmod\{a\}$ for all {{mvar | k}} relatively prime to {{mvar | a}}. By the consequence of minimality proved above, we have $\backslash lambda(a)\backslash ,|\backslash ,\backslash lambda(b)$.

For all positive integers {{mvar | a}} and {{mvar | b}} it holds that

:$\backslash lambda(\backslash mathrm\{lcm\}(a,b))\; =\; \backslash mathrm\{lcm\}(\backslash lambda(a),\; \backslash lambda(b))$.

This is an immediate consequence of the recurrence for the Carmichael function.

If $r\_\{\backslash mathrm\{max\}\}=\backslash max\_i\backslash \{r\_i\backslash \}$ is the biggest exponent in the prime factorization $n=\; p\_1^\{r\_1\}p\_2^\{r\_2\}\; \backslash cdots\; p\_\{k\}^\{r\_k\}$ of {{mvar | n}}, then for all {{mvar | a}} (including those not coprime to {{mvar | n}}) and all {{math | r ≥ r_max}},

:$a^r\; \backslash equiv\; a^\{\backslash lambda(n)+r\}\; \backslash pmod\; n.$

In particular, for square-free {{mvar | n}} ({{math | r_max {{=}} 1}}), for all {{mvar | a}} we have

:$a\; \backslash equiv\; a^\{\backslash lambda(n)+1\}\; \backslash pmod\; n.$

For any {{math | n ≥ 16}}:Theorem 3 in Erdős (1991)Sándor & Crstici (2004) p.194

:$\backslash frac\{1\}\{n\}\; \backslash sum\_\{i\; \backslash leq\; n\}\; \backslash lambda\; (i)\; =\; \backslash frac\{n\}\{\backslash ln\; n\}\; e^\{B\; (1+o(1))\; \backslash ln\backslash ln\; n\; /\; (\backslash ln\backslash ln\backslash ln\; n)\; \}$

(called Erdős approximation in the following) with the constant

:$B\; :=\; e^\{-\backslash gamma\}\; \backslash prod\_\{p\backslash in\backslash mathbb\; P\}\; \backslash left(\{1\; -\; \backslash frac\{1\}\{(p-1)^2(p+1)\}\}\backslash right)\; \backslash approx\; 0.34537$

and {{math | γ ≈ 0.57721}}, the Euler–Mascheroni constant.

The following table gives some overview over the first {{math | 1=2²⁶ – 1 = {{val|fmt=gaps|67108863}}}} values of the {{mvar | λ}} function, for both, the exact average and its Erdős-approximation.

Additionally given is some overview over the more easily accessible {{nowrap|“logarithm over logarithm” values}} {{math | 1=LoL(n) := {{sfrac|ln λ(n)|ln n}}}} with

• {{math | LoL(n) > {{sfrac|4|5}} ⇔ λ(n) > n^{{{sfrac|4|5}}}}}.

There, the table entry in row number 26 at column

• {{math | % LoL > {{sfrac|4|5}}}} {{pad|1em}} → 60.49

indicates that 60.49% (≈ {{val|fmt=gaps|40000000}}) of the integers {{math | 1 ≤ n ≤ {{val|fmt=gaps|67108863}}}} have {{math | λ(n) > n^{{{sfrac|4|5}}}}} meaning that the majority of the {{mvar | λ}} values is exponential in the length {{math | l :{{=}} log₂(n)}} of the input {{mvar | n}}, namely

:$\backslash left(2^\backslash frac45\backslash right)^l\; =\; 2^\backslash frac\{4l\}\{5\}\; =\; \backslash left(2^l\backslash right)^\backslash frac45\; =\; n^\backslash frac45.$

:

For all numbers {{mvar | N}} and all but {{math | o(N)}}Theorem 2 in Erdős (1991) 3. Normal order. (p.365) positive integers {{math | n ≤ N}} (a "prevailing" majority):

:$\backslash lambda(n)\; =\; \backslash frac\{n\}\; \{(\backslash ln\; n)^\{\backslash ln\backslash ln\backslash ln\; n\; +\; A\; +\; o(1)\}\}$

with the constant

:$A\; :=\; -1\; +\; \backslash sum\_\{p\backslash in\backslash mathbb\; P\}\; \backslash frac\{\backslash ln\; p\}\{(p-1)^2\}\; \backslash approx\; 0.2269688$

For any sufficiently large number {{mvar | N}} and for any {{math | Δ ≥ (ln ln N)³}}, there are at most

:$N\backslash exp\backslash left(-0.69(\backslash Delta\backslash ln\backslash Delta)^\backslash frac13\backslash right)$

positive integers {{math | n ≤ N}} such that {{math | λ(n) ≤ ne^−Δ}}.Theorem 5 in Friedlander (2001)

For any sequence {{math | n₁ < n₂ < n₃ < ⋯}} of positive integers, any constant {{math | 0 < c < {{sfrac|1|ln 2}}}}, and any sufficiently large {{mvar | i}}:Theorem 1 in Erdős (1991)Sándor & Crstici (2004) p.193

:$\backslash lambda(n\_i)\; >\; \backslash left(\backslash ln\; n\_i\backslash right)^\{c\backslash ln\backslash ln\backslash ln\; n\_i\}.$

For a constant {{mvar | c}} and any sufficiently large positive {{mvar | A}}, there exists an integer {{math | n > A}} such that

:

Moreover, {{mvar | n}} is of the form

:$n=\backslash mathop\{\backslash prod\_\{q\; \backslash in\; \backslash mathbb\; P\}\}\_\{(q-1)|m\}q$

for some square-free integer {{math | m < (ln A)^{c ln ln ln A}}}.

The set of values of the Carmichael function has counting function{{cite journal | arxiv=1408.6506 | title=The image of Carmichael's λ-function | first1=Kevin | last1=Ford | first2=Florian | last2=Luca | first3=Carl | last3=Pomerance | date=27 August 2014 | doi=10.2140/ant.2014.8.2009 | volume=8 | issue=8 | journal=Algebra & Number Theory | pages=2009–2026| s2cid=50397623 }}

:$\backslash frac\{x\}\{(\backslash ln\; x)^\{\backslash eta+o(1)\}\}\; ,$

where

:$\backslash eta=1-\backslash frac\{1+\backslash ln\backslash ln2\}\{\backslash ln2\}\; \backslash approx\; 0.08607$

The Carmichael function is important in cryptography due to its use in the RSA encryption algorithm.

For {{math | n {{=}} p}}, a prime, Theorem 1 is equivalent to Fermat's little theorem:

:$a^\{p-1\}\backslash equiv1\backslash pmod\{p\}\backslash qquad\backslash text\{for\; all\; \}a\backslash text\{\; coprime\; to\; \}p.$

For prime powers {{math | p^r}}, {{math | r > 1}}, if

:$a^\{p^\{r-1\}(p-1)\}=1+hp^r$

holds for some integer {{mvar | h}}, then raising both sides to the power {{mvar | p}} gives

:$a^\{p^r(p-1)\}=1+h\text{'}p^\{r+1\}$

for some other integer $h\text{'}$. By induction it follows that $a^\{\backslash varphi(p^r)\}\backslash equiv1\backslash pmod\{p^r\}$ for all {{mvar | a}} relatively prime to {{mvar | p}} and hence to {{math | p^r}}. This establishes the theorem for {{math | n {{=}} 4}} or any odd prime power.

For {{mvar | a}} coprime to (powers of) 2 we have {{math | a {{=}} 1 + 2h₂}} for some integer {{math | h₂}}. Then,

:$a^2\; =\; 1+4h\_2(h\_2+1)\; =\; 1+8\backslash binom\{h\_2+1\}\{2\}=:1+8h\_3$,

where $h\_3$ is an integer. With {{math | 1=r = 3}}, this is written

:$a^\{2^\{r-2\}\}\; =\; 1+2^r\; h\_r.$

Squaring both sides gives

:$a^\{2^\{r-1\}\}=\backslash left(1+2^r\; h\_r\backslash right)^2=1+2^\{r+1\}\backslash left(h\_r+2^\{r-1\}h\_r^2\backslash right)=:1+2^\{r+1\}h\_\{r+1\},$

where $h\_\{r+1\}$ is an integer. It follows by induction that

:$a^\{2^\{r-2\}\}=a^\{\backslash frac\{1\}\{2\}\backslash varphi(2^r)\}\backslash equiv\; 1\backslash pmod\{2^r\}$

for all $r\backslash ge3$ and all {{mvar | a}} coprime to $2^r$.Carmichael (1914) pp.38–39

By the unique factorization theorem, any {{math | n > 1}} can be written in a unique way as

:$n=\; p\_1^\{r\_1\}p\_2^\{r\_2\}\; \backslash cdots\; p\_\{k\}^\{r\_k\}$

where {{math | p₁ < p₂ < ... < p_k}} are primes and {{math | r₁, r₂, ..., r_k}} are positive integers. The results for prime powers establish that, for $1\backslash le\; j\backslash le\; k$,

:$a^\{\backslash lambda\backslash left(p\_j^\{r\_j\}\backslash right)\}\backslash equiv1\; \backslash pmod\{p\_j^\{r\_j\}\}\backslash qquad\backslash text\{for\; all\; \}a\backslash text\{\; coprime\; to\; \}n\backslash text\{\; and\; hence\; to\; \}p\_i^\{r\_i\}.$

From this it follows that

:$a^\{\backslash lambda(n)\}\backslash equiv1\; \backslash pmod\{p\_j^\{r\_j\}\}\backslash qquad\backslash text\{for\; all\; \}a\backslash text\{\; coprime\; to\; \}n,$

where, as given by the recurrence,

:$\backslash lambda(n)\; =\; \backslash operatorname\{lcm\}\backslash Bigl(\backslash lambda\backslash left(p\_1^\{r\_1\}\backslash right),\backslash lambda\backslash left(p\_2^\{r\_2\}\backslash right),\backslash ldots,\backslash lambda\backslash left(p\_k^\{r\_k\}\backslash right)\backslash Bigr).$

From the Chinese remainder theorem one concludes that

:$a^\{\backslash lambda(n)\}\backslash equiv1\; \backslash pmod\{n\}\backslash qquad\backslash text\{for\; all\; \}a\backslash text\{\; coprime\; to\; \}n.$

• Carmichael number

• {{cite journal |first1=Paul |last1= Erdős |author1-link=Paul Erdős |first2=Carl |last2=Pomerance |author2-link=Carl Pomerance |first3=Eric |last3=Schmutz |year=1991 |title=Carmichael's lambda function |journal=Acta Arithmetica |volume=58 |issue= 4 |pages=363–385 |mr=1121092 | zbl=0734.11047 | issn=0065-1036 |doi=10.4064/aa-58-4-363-385|doi-access=free }}
• {{cite journal |first1=John B. |last1=Friedlander |author1-link=John Friedlander |first2=Carl |last2=Pomerance |first3=Igor E. |last3=Shparlinski |year=2001 |title=Period of the power generator and small values of the Carmichael function |journal=Mathematics of Computation |volume=70 |number=236 |pages=1591–1605, 1803–1806 |mr=1836921 | zbl=1029.11043 | issn=0025-5718 |doi=10.1090/s0025-5718-00-01282-5|doi-access=free }}
• {{cite book | last1=Sándor | first1=Jozsef | last2=Crstici | first2=Borislav | title=Handbook of number theory II | location=Dordrecht | publisher=Kluwer Academic | year=2004 | isbn=978-1-4020-2546-4 | pages=32–36, 193–195 | zbl=1079.11001}}
• {{Gutenberg|no=13693|name=The Theory of Numbers|last=Carmichael|first=Robert D.|origyear=1914}}

{{Totient}}

Category:Modular arithmetic

Category:Functions and mappings