Carmichael function: Difference between revisions

Revision as of 15:21, 30 March 2022

Latest revision as of 01:52, 8 August 2025

(32 intermediate revisions by 22 users not shown)

Line 1:

{{Short description|Function in mathematical number theory}}

In [[File:carmichaelLambda.svg|thumb|upright=2|Carmichaelnumber {{mvartheory]], |a λ}}branch of [[mathematics]], the '''Carmichael function:''' {{math | ''λ''(''n'')}} forof a [[positive integer]] {{mathmvar | 1 ≤ ''n'' ≤ 1000}} (comparedis tothe Eulersmallest positive integer {{mvar | φm}} function)]]such that

:<math>a^m \equiv 1 \pmod{n}</math>

In [[number theory]], a branch of [[mathematics]], the '''Carmichael function''' {{math | ''λ''(''n'')}} of a [[positive integer]] {{mvar | n}} is the smallest positive integer {{mvar | m}} such that

holds for every integer {{mvar | a}} [[coprime]] to {{mvar | n}}. In algebraic terms, {{math | ''λ''(''n'')}} is the [[exponent of a group|exponent]] of the [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{mvar | n}}]]. As this is a [[Abelian group#Finite abelian groups|finite abelian group]], there must exist an element whose [[Cyclic group#Definition and notation|order]] equals the exponent, {{math | ''λ''(''n'')}}. Such an element is called a '''primitive {{math | ''λ''}}-root modulo {{mvar | n}}'''.

:{{bigmath|''a^m'' ≡ 1 {{pad|1em}} ([[modular arithmetic|mod]] ''n'')}}

for every integer {{mvar | a}} between 1 and {{mvar | n}} that is [[coprime]] to {{mvar | n}}. In algebraic terms, {{math | ''λ''(''n'')}} is the [[exponent of a group|exponent]] of the [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{mvar | n}}]].

[[File:carmichaelLambda.svg|thumb|upright=2|Carmichael {{mvar | λ}} function: {{math | ''λ''(''n'')}} for {{math | 1 ≤ ''n'' ≤ 1000}} (compared to Euler {{mvar | φ}} function)|none]]

The Carmichael function is named after the American mathematician [[Robert Daniel Carmichael|Robert Carmichael]] and is also known as '''Carmichael's λ function''', the '''reduced totient function''', and the '''least universal exponent function'''.

The Carmichael function is named after the American mathematician [[Robert Daniel Carmichael|Robert Carmichael]] who defined it in 1910.<ref>

The following table compares the first 36 values of {{math | ''λ''(''n'')}} {{OEIS|id=A002322}} with [[Euler's totient function]] {{mvar | φ}} (in '''bold''' if they are different; the {{mvar | n}}s such that they are different are listed in {{oeis|A033949}}).

{{cite journal |first1=Robert Daniel |last1=Carmichael |year=1910 |title=Note on a new number theory function |journal=Bulletin of the American Mathematical Society |volume=16 |number=5 |pages=232–238 |doi=10.1090/S0002-9904-1910-01892-9|doi-access=free }}

</ref> It is also known as '''Carmichael's λ function''', the '''reduced totient function''', and the '''least universal exponent function'''.

The order of the multiplicative group of integers modulo {{mvar | n}} is {{math | ''φ''(''n'')}}, where {{mvar | φ}} is [[Euler's totient function]]. Since the order of an element of a finite group divides the order of the group, {{math | ''λ''(''n'')}} divides {{math | ''φ''(''n'')}}. The following table compares the first 36 values of {{math | ''λ''(''n'')}} {{OEIS|id=A002322}} and {{math | ''φ''(''n'')}} (in '''bold''' if they are different; the values of{{mvar | n}} such that they are different are listed in {{oeis|A033949}}).

{| class="wikitable" style="text-align: center;"

Line 57 ⟶ 60:

==Numerical examples==

# Carmichael's function at 5 is 4,* {{math | ''λn''(5) {{=}} 45}},. becauseThe forset anyof numbernumbers <math>0<a<5</math>less than and coprime to 5, i.e.is <{{math>a\in \| {1, 2, 3, 4\}~,</math>}}. thereHence isEuler's <math>a^mtotient \equivfunction 1has \,(\text{mod } 5)</math> with <math>m=4,</math> namely,value {{math | 1^1⋅4''φ''(5) {{=}} 1⁴ ≡ 1 (mod 5)}}, {{mathand |the 2⁴value {{=}}of 16Carmichael's ≡ 1 (mod 5)}}function, {{math | 3⁴ {{=}} 81 ≡ 1 ''λ''(mod 5)}}, andmust {{mathbe |a 4^2⋅2[[divisor]] {{=}}of 16² ≡ 1² (mod 5)}}4. The Anddivisor this1 {{mathdoes |not ''m'' {{=}} 4}} issatisfy the smallestdefinition exponentof withCarmichael's this property,function becausesince <math>2a^2 =41 \not\equiv 1 \,(\textpmod{mod 5}</math> except for <math>a\equiv1\pmod{5)}</math>. (andNeither does 2 since <math>2^2 \equiv 3^2 =\equiv 94 \not\equiv 1 \,(\textpmod{mod 5} 5)</math> as well.)<br />Moreover, Euler's [[totient function]] at 5 is 4,Hence {{math | ''φλ''(5) {{=}} 4}}. Indeed, because there are exactly <math>1^4 numbers less than and coprime to 5 (1,\equiv 2,^4\equiv 3, and^4\equiv 4). [[Euler's theorem]] assures that ^4\equiv1\pmod{{math | ''a''<sup>45}</supmath>. ≡Both 12 (modand 5)}}3 forare allprimitive {{mvar | aλ}}-roots coprime tomodulo 5, and 4also is[[Primitive theroot smallestmodulo suchn|primitive exponentroots]] modulo 5.

# Carmichael's function at 8 is 2,* {{math | ''λn''(8) {{=}} 28}},. becauseThe forset anyof numbernumbers {{mvarless |than a}}and coprime to 8, i.e.is <{{math>a\in \| {1, 3, 5, 7\}~,</math> it}}. holds thatHence {{math | ''aφ''² ≡ 1 (mod 8)}}. Namely, {{math | 1^1⋅2 {{=}} 1² ≡ 1 (mod 8)4}}, {{math | 3² {{=}} 9 ≡ 1 (mod 8)}},and {{math | 5² {{=}} 25 ≡ 1 ''λ''(mod 8)}} andmust {{mathbe |a 7²divisor {{=}}of 49 ≡ 1 (mod 8)}}4.<br />Euler'sIn [[totient function]] at 8 is 4,fact {{math | ''φλ''(8) {{=}} 42}}, becausesince there are exactly 4 numbers less than and coprime to 8 (<math>1,^2\equiv 3,^2\equiv 5, and^2\equiv 7). Moreover, [[Euler's theorem]] assures that ^2\equiv1\pmod{{math | ''a''<sup>48}</supmath>. ≡The 1 (mod 8)}} for allprimitive {{mvar | aλ}}-roots coprime tomodulo 8 are 3, but5, 4and is7. notThere theare smallestno suchprimitive exponentroots modulo 8.

== ComputingRecurrence for {{math | ''λ''(''n'')}} with Carmichael's theorem ==

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

:<math>\lambda(n) = \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}</math>

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

:<math>\varphi(p^r) {{=}} p^{r-1}(p-1).</math>

== Carmichael's theorems ==

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

{{anchor|Carmichael's theorem}}

:<math> n= p_1^{r_1}p_2^{r_2} \cdots p_{k}^{r_k} </math>

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 <math>a^m\equiv 1\pmod{n}</math> for all {{mvar | a}} relatively prime to {{mvar | n}}.

where {{math | ''p''₁ < ''p''₂ < ... < ''p_k''}} are [[prime]]s and {{math | ''r''₁, ''r''₂, ..., ''r_k''}} are positive integers. Then {{math | ''λ''(''n'')}} is the [[least common multiple]] of the {{mvar | λ}} of each of its prime power factors:

{{Math theorem |name=Theorem 1|math_statement=If {{mvar | a}} is relatively prime to {{mvar | n}} then <math>a^{\lambda(n)}\equiv 1\pmod{n}</math>.<ref>Carmichael (1914) p.40</ref>}}

:<math>\lambda(n) = \operatorname{lcm}\left(\lambda\left(p_1^{r_1}\right),\lambda\left(p_2^{r_2}\right),\ldots,\lambda\left(p_k^{r_k}\right)\right).</math>

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 <math>a^{\lambda(n)}</math> is the least power of {{mvar | a}} congruent to 1 (mod {{mvar | n}}) a ''primitive λ-root modulo n''.<ref>Carmichael (1914) p.54</ref> (This is not to be confused with a [[primitive root modulo n|primitive root modulo {{mvar | n}}]], which Carmichael sometimes refers to as a primitive <math>\varphi</math>-root modulo {{mvar | n}}.)

This can be proved using the [[Chinese remainder theorem]].

{{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 <math>\varphi(\lambda(n))</math> primitive {{mvar | λ}}-roots that are congruent to powers of {{mvar | g}}.<ref>Carmichael (1914) p.55</ref>}}

If {{mvar | g}} is one of the primitive {{mvar | λ}}-roots guaranteed by the theorem, then <math>g^m\equiv1\pmod{n}</math> has no positive integer solutions {{mvar | m}} less than {{math | ''λ''(''n'')}}, showing that there is no positive {{math | ''m'' < ''λ''(''n'')}} such that <math>a^m\equiv 1\pmod{n}</math> 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}}.<ref>Carmichael (1914) p.56</ref> For example, if {{math | ''n'' {{=}} 15}}, then {{math | ''λ''(''n'') {{=}} 4}} while <math>\varphi(n)=8</math> and <math>\varphi(\lambda(n))=2</math>. There are four primitive {{mvar | λ}}-roots modulo 15, namely 2, 7, 8, and 13 as <math>1\equiv2^4\equiv8^4\equiv7^4\equiv13^4</math>. 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 <math>4\equiv2^2\equiv8^2\equiv7^2\equiv13^2</math>), 11, and 14, are not primitive {{mvar | λ}}-roots modulo 15.

'''Carmichael's theorem''' explains how to compute {{mvar | λ}} of a prime power {{math | ''p''^''r''}}: for a power of an odd prime and for 2 and 4, {{math | ''λ''(''p''^''r'')}} is equal to the [[Euler totient]] {{math | ''φ''(''p''^''r'')}}; for powers of 2 greater than 4 it is equal to half of the Euler totient:

For a contrasting example, if {{math | ''n'' {{=}} 9}}, then <math>\lambda(n)=\varphi(n)=6</math> and <math>\varphi(\lambda(n))=2</math>. 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 <math>\varphi</math>-roots modulo 9.

:<math>\lambda(p^r) = \begin{cases}

\varphi\left(p^r\right) &\mbox{if }p^r = 2,3^r,4,5^r,7^r,11^r,13^r,17^r,19^r,23^r,29^r,31^r,\dots\\

\tfrac12\varphi\left(p^r\right)&\text{if }p^r = 8,16,32,64,128,256,\dots

\end{cases}</math>

Euler's function for prime powers {{math | ''p''^''r''}} is given by

:<math>\varphi(p^r) = p^{r-1}(p-1).</math>

==Properties of the Carmichael function==

Line 82 ⟶ 89:

:<math>m \mid n.</math>

===OrderA consequence of elementsminimality moduloof ''{{mvarmath | ''λ''(''n}}'')}}===

Let {{mvar | a}} and {{mvar | n}} be [[coprime]] and let {{mvar | m}} be the smallest exponent with {{math | ''a^m'' ≡ 1 (mod ''n'')}}, then it holds that

:<math>m \,|\, \lambda(n)</math>.

That is, the [[Multiplicative order|order]] {{mvar | m :{{=}} ord_''n''(''a'')}} of a [[unit (ring theory)|unit]] {{mvar | a}} in the ring of integers modulo {{mvar | n}} divides {{math | ''λ''(''n'')}} and

:<math> \lambda(n) = \max\{\operatorname{ord}_n(a) \, \colon \, \gcd(a,n)=1\}</math>

===Minimality===

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

Line 94 ⟶ 95:

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

:<math>a^r = 1^k \cdot a^r \equiv \left(a^{\lambda(n)}\right)^k\cdot a^r = a^{k\lambda(n)+r} = a^m \equiv 1\pmod{n}</math>

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 suchexponent numberfor which the congruence holds for all {{mvar | a}} coprime with {{mvar | n}}.

=== {{math | ''λ''(''n'')}} divides {{math | ''φ''(''n'')}} ===

Line 107 ⟶ 108:

'''Proof.'''

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

===Composition===

Line 113 ⟶ 114:

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

:<math>\lambda(\mathrm{lcm}(a,b)) = \mathrm{lcm}(\lambda(a), \lambda(b))</math>.

This is an immediate consequence of the recursiverecurrence definition offor the Carmichael function.

<!--

Proof goes as follows:

Line 130 ⟶ 131:

===Exponential cycle length===

If <math>r_{\mathrm{mvar | nmax}}=\max_i\{r_i\}</math> hasis maximumthe primebiggest exponent in the prime factorization <math> n= p_1^{r_1}p_2^{mathr_2} |\cdots p_{k}^{r_k} ''r''<sub>max</submath>}} underof prime{{mvar factorization| n}}, then for all {{mvar | a}} (including those not coprime to {{mvar | n}}) and all {{math | ''r'' ≥ ''r''_max}},

:<math>a^r \equiv a^{r+\lambda(n)+r} \pmod n.</math>

In particular, for [[Square-free integer|square-free]] {{mvar | n}} ({{math | ''r''_max {{=}} 1}}), for all {{mvar | a}} we have

:<math>a \equiv a^{\lambda(n)+1} \pmod n.</math>

===Extension for powers of two===

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

:<math>a^2 = 1+4h(h+1) = 1+8C</math>

where we take advantage of the fact that {{math | ''C'' :{{=}} {{sfrac|(''h'' + 1)''h''|2}}}} is an integer.

So, for {{math | 1=''k'' = 3}}, {{mvar | h}} an integer:

:<math>\begin{align}

a^{2^{k-2}}&=1+2^k h \\

a^{2^{k-1}}&=\left(1+2^k h\right)^2=1+2^{k+1}\left(h+2^{k-1}h^2\right)

\end{align}</math>

By induction, when {{math | ''k'' ≥ 3}}, we have

:<math>a^{2^{k-2}}\equiv 1\pmod{2^k}.</math>

It provides that {{math | ''λ''(2^''k'')}} is at most {{math | 2^{''k'' − 2}}}.<ref name="car">{{cite book|first=Robert Daniel|last=Carmichael|title=The Theory of Numbers|___location=Nabu Press|isbn=1144400341|url=http://www.gutenberg.org/ebooks/13693}}{{page needed|date=May 2020}}</ref>

===Average value===

Line 241 ⟶ 222:

===Minimal order===

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}}:<ref name="Theorem 1 in Erdős (1991)">Theorem 1 in Erdős (1991)</ref><ref name=HBII193>Sándor & Crstici (2004) p.193</ref>

:<math>\lambda(n_i) > \left(\ln n_i\right)^{c\ln\ln\ln n_i}.</math>

Line 250 ⟶ 231:

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

:<math>n=\mathop{\prod_{q \in \mathbb P}}_{(q-1)|m}q</math>

for some square-free integer {{math | ''m'' < (ln ''A'')^{''c'' ln ln ln ''A''}}}.<ref name="Theorem 1 in Erdős (1991)"/>

===Image of the function===

The set of values of the Carmichael function has counting function<ref>{{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 }}</ref>

:<math>\frac{x}{(\ln x)^{\eta+o(1)}} ,</math>

where

Line 261 ⟶ 242:

The Carmichael function is important in [[cryptography]] due to its use in the [[RSA (cryptosystem)|RSA encryption algorithm]].

==Proof of Theorem 1==

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

:<math>a^{p-1}\equiv1\pmod{p}\qquad\text{for all }a\text{ coprime to }p.</math>

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

:<math>a^{p^{r-1}(p-1)}=1+hp^r</math>

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

:<math>a^{p^r(p-1)}=1+h'p^{r+1}</math>

for some other integer <math>h'</math>. By induction it follows that <math>a^{\varphi(p^r)}\equiv1\pmod{p^r}</math> 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.

===Sharpening the result for higher powers of two===

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

:<math>a^2 = 1+4h_2(h_2+1) = 1+8\binom{h_2+1}{2}=:1+8h_3</math>,

where <math>h_3</math> is an integer. With {{math | 1=''r'' = 3}}, this is written

:<math>a^{2^{r-2}} = 1+2^r h_r.</math>

Squaring both sides gives

:<math>a^{2^{r-1}}=\left(1+2^r h_r\right)^2=1+2^{r+1}\left(h_r+2^{r-1}h_r^2\right)=:1+2^{r+1}h_{r+1},</math>

where <math>h_{r+1}</math> is an integer. It follows by induction that

:<math>a^{2^{r-2}}=a^{\frac{1}{2}\varphi(2^r)}\equiv 1\pmod{2^r}</math>

for all <math>r\ge3</math> and all {{mvar | a}} coprime to <math>2^r</math>.<ref>Carmichael (1914) pp.38–39</ref>

===Integers with multiple prime factors===

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

:<math> n= p_1^{r_1}p_2^{r_2} \cdots p_{k}^{r_k} </math>

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 <math>1\le j\le k</math>,

:<math>a^{\lambda\left(p_j^{r_j}\right)}\equiv1 \pmod{p_j^{r_j}}\qquad\text{for all }a\text{ coprime to }n\text{ and hence to }p_i^{r_i}.</math>

From this it follows that

:<math>a^{\lambda(n)}\equiv1 \pmod{p_j^{r_j}}\qquad\text{for all }a\text{ coprime to }n,</math>

where, as given by the recurrence,

:<math>\lambda(n) = \operatorname{lcm}\Bigl(\lambda\left(p_1^{r_1}\right),\lambda\left(p_2^{r_2}\right),\ldots,\lambda\left(p_k^{r_k}\right)\Bigr).</math>

From the [[Chinese remainder theorem]] one concludes that

:<math>a^{\lambda(n)}\equiv1 \pmod{n}\qquad\text{for all }a\text{ coprime to }n.</math>

==See also==

Line 272 ⟶ 285:

* {{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}}

* {{cite book Gutenberg| lastno=Carmichael |first=R. D.13693|titlename=The Theory of Numbers|___locationlast=Nabu PressCarmichael|isbnfirst=978-1144400345|url=http://wwwRobert D.gutenberg.org/ebooks/13693|dateorigyear=2004-10-101914}}

{{Totient}}