Carmichael function: Difference between revisions

Revision as of 14:43, 1 November 2020

Revision as of 02:42, 17 February 2021

Line 1:

[[File:carmichaelLambda.svg|thumb|upright=2|Carmichael {{mvar|λ}} function: {{math|''λ''(''n'')}} for {{math|1 ≤ ''n'' ≤ 1000}} (compared to Euler {{mvar|φ}} function)]]{{Short description|function of interest in number theory}}

In [[number theory]], a branch of [[mathematics]], the '''File:carmichaelLambda.svg|thumb|upright=2|Carmichael function''' associates to every [[positive integer]] {{mvar |n λ}} a positive integerfunction: {{math | ''λ''(''n'')}}, definedfor as{{math the| smallest1 positive≤ integer''n'' ≤ 1000}} (compared to Euler {{mvar |m φ}} such thatfunction)]]

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

:{{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}}]].

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

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

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

|-

! scope="col" | {{mvar | n}}

! scope="col" | 1

! scope="col" | 2

Line 48 ⟶ 49:

! scope="col" | 36

|-

! scope="row" | {{math | ''λ''(''n'')}}

| 1 || 1 || 2 || 2 || 4 || 2 || 6 || '''2''' || 6 || 4 || 10 || '''2''' || 12 || 6 || '''4''' || '''4''' || 16 || 6 || 18 || '''4''' || '''6''' || 10 || 22 || '''2''' || 20 || 12 || 18 || '''6''' || 28 || '''4''' || 30 || '''8''' || '''10''' || 16 || '''12''' || '''6'''

|-

! scope="row" | {{math | ''φ''(''n'')}}

| 1 || 1 || 2 || 2 || 4 || 2 || 6 || '''4''' || 6 || 4 || 10 || '''4''' || 12 || 6 || '''8''' || '''8''' || 16 || 6 || 18 || '''8''' || '''12''' || 10 || 22 || '''8''' || 20 || 12 || 18 || '''12''' || 28 || '''8''' || 30 || '''16''' || '''20''' || 16 || '''24''' || '''12'''

|}

==Numerical example==

Carmichael's function at 8 is 2, {{math | ''λ''(8) {{=}} 2}}, because for any number {{mvar | a}} coprime to 8 it holds that {{math | ''a''² ≡ 1 (mod 8)}}. Namely, {{math | 1² {{=}} 1 (mod 8)}}, {{math | 3² {{=}} 9 ≡ 1 (mod 8)}}, {{math | 5² {{=}} 25 ≡ 1 (mod 8)}} and {{math | 7² {{=}} 49 ≡ 1 (mod 8)}}. Euler's [[totient function]] at 8 is 4, {{math | ''φ''(8) {{=}} 4}}, because there are 4 numbers less than and coprime to 8 (1, 3, 5, and 7). [[Euler's theorem]] assures that {{math | ''a''⁴ ≡ 1 (mod 8)}} for all {{mvar | a}} coprime to 8, but 4 is not the smallest such exponent.

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

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 [[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>\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 can be proved using the [[Chinese remainder theorem]].

'''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:

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

Line 73 ⟶ 74:

\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==

===Order of elements modulo ''{{mvar | 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''}}.

'''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 {{math | 1=''r'' = 0}}, since {{math | ''r'' < ''λ''(''n'')}} and {{math | ''λ''(''n'')}} the minimal positive such number.

===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}

Line 105 ⟶ 106:

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

=== {{math | ''λ''(''n'')}} divides {{math | ''φ''(''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.

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

===Divisibility===

Line 127 ⟶ 128:

===Composition===

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 recursive definition of the Carmichael function.

Line 146 ⟶ 147:

===Exponential cycle length===

If {{mvar | n}} has maximum prime exponent {{math | ''r''_max}} under prime factorization, 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)} \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>

Line 156 ⟶ 157:

===Average value===

For any {{math | ''n'' ≥ 16}}:<ref>Theorem 3 in Erdős (1991)</ref><ref name=HBII194>Sándor & Crstici (2004) p.194</ref>

:<math>\frac{1}{n} \sum_{i \leq n} \lambda (i) = \frac{n}{\ln n} e^{B (1+o(1)) \ln\ln n / (\ln\ln\ln n) }</math>

Line 163 ⟶ 164:

:<math>B := e^{-\gamma} \prod_{p\in\mathbb P} \left({1 - \frac{1}{(p-1)^2(p+1)}}\right) \approx 0.34537 </math>

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

:<math>\left(2^\frac45\right)^l = 2^\frac{4l}{5} = \left(2^l\right)^\frac45 = n^\frac45.</math>

:{| class="wikitable" style="text-align:right"

|- style="vertical-align:top"

! {{mvar | ν}} || {{math | 1=''n'' = 2^''ν'' – 1}} || sum<br /><math>\sum_{i\le n} \lambda(i) </math> || average<br /><math>\tfrac1n \sum_{i\le n} \lambda(i) </math> || Erdős average || Erdős /<br>exact average || {{math | LoL}} average || % {{math | LoL}} > {{sfrac|4|5}} || % {{math | LoL}} > {{sfrac|7|8}}

|-

|5||31||270||8.709677||68.643||7.8813||0.678244||41.94 ||35.48

Line 224 ⟶ 225:

===Prevailing interval===

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

:<math>\lambda(n) = \frac{n} {(\ln n)^{\ln\ln\ln n + A + o(1)}}</math>

with the constant<ref name=HBII194/>

Line 232 ⟶ 233:

===Lower bounds===

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

:<math>N\exp\left(-0.69(\Delta\ln\Delta)^\frac13\right)</math>

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

===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>

===Small values===

For a constant {{mvar | c}} and any sufficiently large positive {{mvar | A}}, there exists an integer {{math | ''n'' > ''A''}} such that<ref name=HBII193/>

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

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===

Line 256 ⟶ 257:

==Use in cryptography==

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

==See also==