View source for Carmichael function

{{Short description|Function in mathematical number theory}}
[[File:carmichaelLambda.svg|thumb|upright=2|Carmichael {{mvar | λ}} function: {{math | ''λ''(''n'')}} for {{math | 1 ≤ ''n'' ≤ 1000}} (compared to Euler {{mvar | φ}} function)]]
In [[Number theory|number theory]], a branch of [[Mathematics|mathematics]], the '''Carmichael function''' {{math | ''λ''(''n'')}} of a positive integer {{mvar | n}} is the smallest positive integer {{mvar | m}} such that
:<math>a^m \equiv 1 \pmod{n}</math>
holds for every integer {{mvar | a}} coprime to {{mvar | n}}. In algebraic terms, {{math | ''λ''(''n'')}} is the 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}}'''.

The Carmichael function is named after the American mathematician [[Biography:Robert Daniel Carmichael|Robert Carmichael]] who defined it in 1910.<ref>
{{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 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
! scope="col" | 3
! scope="col" | 4
! scope="col" | 5
! scope="col" | 6
! scope="col" | 7
! scope="col" | 8
! scope="col" | 9
! scope="col" | 10
! scope="col" | 11
! scope="col" | 12
! scope="col" | 13
! scope="col" | 14
! scope="col" | 15
! scope="col" | 16
! scope="col" | 17
! scope="col" | 18
! scope="col" | 19
! scope="col" | 20
! scope="col" | 21
! scope="col" | 22
! scope="col" | 23
! scope="col" | 24
! scope="col" | 25
! scope="col" | 26
! scope="col" | 27
! scope="col" | 28
! scope="col" | 29
! scope="col" | 30
! scope="col" | 31
! scope="col" | 32
! scope="col" | 33
! scope="col" | 34
! scope="col" | 35
! 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 examples==
# Carmichael's function at 5 is 4, {{math | ''λ''(5) {{=}} 4}}, because for any number <math>0<a<5</math> coprime to 5, i.e. <math>a\in \{1, 2, 3, 4\}~,</math> there is <math>a^m \equiv 1 \,(\text{mod } 5)</math> with <math>m=4,</math> namely, {{math | 1<sup>1⋅4</sup> {{=}} 1<sup>4</sup> ≡ 1 (mod 5)}}, {{math | 2<sup>4</sup> {{=}} 16 ≡ 1 (mod 5)}}, {{math | 3<sup>4</sup> {{=}} 81 ≡ 1 (mod 5)}} and {{math | 4<sup>2⋅2</sup> {{=}} 16<sup>2</sup> ≡ 1<sup>2</sup> (mod 5)}}.  And this {{math | ''m'' {{=}} 4}} is the smallest exponent with this property, because <math>2^2 =4 \not\equiv 1 \,(\text{mod } 5)</math> (and <math>3^2 = 9 \not\equiv 1 \,(\text{mod } 5)</math> as well.)<br />Moreover, Euler's totient function at 5 is 4, {{math | ''φ''(5) {{=}} 4}}, because there are exactly 4 numbers less than and coprime to 5 (1, 2, 3, and 4).  [[Euler's theorem]] assures that {{math | ''a''<sup>4</sup> ≡ 1 (mod 5)}} for all {{mvar | a}} coprime to 5, and 4 is the smallest such exponent. Both 2 and 3 are primitive {{mvar | λ}}-roots modulo 5 and also [[Primitive root modulo n|primitive roots]] modulo 5.
# Carmichael's function at 8 is 2, {{math | ''λ''(8) {{=}} 2}}, because for any number {{mvar | a}} coprime to 8, i.e. <math>a\in \{1, 3, 5, 7\}~,</math> it holds that {{math | ''a''<sup>2</sup> ≡ 1 (mod 8)}}. Namely, {{math | 1<sup>1⋅2</sup> {{=}} 1<sup>2</sup> ≡ 1 (mod 8)}}, {{math | 3<sup>2</sup> {{=}} 9 ≡ 1 (mod 8)}}, {{math | 5<sup>2</sup> {{=}} 25 ≡ 1 (mod 8)}} and {{math | 7<sup>2</sup> {{=}} 49 ≡ 1 (mod 8)}}.<br />Euler's totient function at 8 is 4, {{math | ''φ''(8) {{=}} 4}}, because there are exactly 4 numbers less than and coprime to 8 (1, 3, 5, and 7).  Moreover, [[Euler's theorem]] assures that {{math | ''a''<sup>4</sup> ≡ 1 (mod 8)}} for all {{mvar | a}} coprime to 8, but 4 is not the smallest such exponent. The primitive {{mvar | λ}}-roots modulo 8 are 3, 5, and 7. There are no primitive roots modulo 8.

== Recurrence for {{math | ''λ''(''n'')}} ==
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|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''<sup>''r''</sup>}} with {{math | ''p''}} prime and {{math | ''r'' ≥ 1}}, is given by
:<math>\varphi(p^r) {{=}} p^{r-1}(p-1).</math>

== Carmichael's theorems ==
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}}.
{{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>Carmichaael (1914) p.40</ref>}}
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}}.)
{{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 t 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.

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.

==Properties of the Carmichael function==
In this section, an [[Integer|integer]] <math>n</math> is divisible by a nonzero integer <math>m</math> if there exists an integer <math>k</math> such that <math>n = km</math>. This is written as
:<math>m \mid n.</math>

===A consequence of minimality of {{math | ''λ''(''n'')}}===

Suppose {{math | ''a<sup>m</sup>'' ≡ 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 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}}.

=== {{math | ''λ''(''n'')}} divides {{math | ''φ''(''n'')}} ===
This follows from elementary [[Group theory|group theory]], because the exponent of any [[Finite group|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 modulo n|primitive root]], which is the case for odd prime powers.

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

===Divisibility===

:<math> a\,|\,b \Rightarrow \lambda(a)\,|\,\lambda(b) </math>

'''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 proved above, we have <math> \lambda(a)\,|\,\lambda(b) </math>.

===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 recurrence for the Carmichael function.
<!--
Proof goes as follows:
Write a and b as product of prime powers
a = p1^x1·...·pt^xt
b = p1^y1·...·pt^yt
lambda(lcm(a,b))
 = lambda(p1^max(x1,y1)·...·pt^max(xt,yt))
 = lcm(lambda(p1^max(x1,y1)), ..., lambda(pt^max(xt,yt)))
 = lcm(lcm(lambda(p1^x1),lambda(p1^y1)), ..., lcm(lambda(pt^xt),lambda(pt^yt)))
 = lcm(lcm(lambda(p1^x1),...,lambda(pt^xt)), lcm(lambda(p1^y1),...,lambda(pt^yt)))
 = lcm(lambda(p1^x1·...·pt^xt), lambda(p1^y1·...·pt^yt))
 = lcm(lambda(a), lambda(b))
-->

===Exponential cycle length===

If <math>r_{\mathrm{max}}=\max_i\{r_i\}</math> is the biggest exponent in the prime factorization <math> n= p_1^{r_1}p_2^{r_2} \cdots p_{k}^{r_k} </math> of {{mvar | n}}, then for all {{mvar | a}} (including those not coprime to {{mvar | n}}) and all {{math | ''r'' ≥ ''r''<sub>max</sub>}},

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

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

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

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

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

:<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<sup>26</sup> – 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''<sup>{{sfrac|4|5}}</sup>}}.
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''<sup>{{sfrac|4|5}}</sup>}} meaning that the majority of the {{mvar | λ}} values is exponential in the length {{math | ''l'' :{{=}} log<sub>2</sub>(''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<sup>''ν''</sup> – 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 
|-
|6||63||964||15.301587||61.414||4.0136||0.699891||38.10 ||30.16 
|-
|7||127||3574||28.141732||86.605||3.0774||0.717291||38.58 ||27.56 
|-
|8||255||12994||50.956863||138.190||2.7119||0.730331||38.82 ||23.53 
|-
|9||511||48032||93.996086||233.149||2.4804||0.740498||40.90 ||25.05 
|-
|10||1023||178816||174.795699||406.145||2.3235||0.748482||41.45 ||26.98 
|-
|11||2047||662952||323.865169||722.526||2.2309||0.754886||42.84 ||27.70 
|-
|12||4095||2490948||608.290110||1304.810||2.1450||0.761027||43.74 ||28.11 
|-
|13||8191||9382764||1145.496765||2383.263||2.0806||0.766571||44.33 ||28.60 
|-
|14||16383||35504586||2167.160227||4392.129||2.0267||0.771695||46.10 ||29.52 
|-
|15||32767||134736824||4111.967040||8153.054||1.9828||0.776437||47.21 ||29.15 
|-
|16||65535||513758796||7839.456718||15225.43{{0}}||1.9422||0.781064||49.13 ||28.17 
|-
|17||131071||1964413592||14987.40066{{0}}||28576.97{{0}}||1.9067||0.785401||50.43 ||29.55 
|-
|18||262143||7529218208||28721.79768{{0}}||53869.76{{0}}||1.8756||0.789561||51.17 ||30.67 
|-
|19||524287||28935644342||55190.46694{{0}}||101930.9{{0|00}}||1.8469||0.793536||52.62 ||31.45 
|-
|20||1048575||111393101150||106232.8409{{0|00}}||193507.1{{0|00}}||1.8215||0.797351||53.74 ||31.83 
|-
|21||2097151||429685077652||204889.9090{{0|00}}||368427.6{{0|00}}||1.7982||0.801018||54.97 ||32.18 
|-
|22||4194303||1660388309120||395867.5158{{0|00}}||703289.4{{0|00}}||1.7766||0.804543||56.24 ||33.65 
|-
|23||8388607||6425917227352||766029.1187{{0|00}}||1345633{{0|.000}}||1.7566||0.807936||57.19 ||34.32 
|-
|24||16777215||24906872655990||1484565.386{{0|000}}||2580070{{0|.000}}||1.7379||0.811204||58.49 ||34.43 
|-
|25||33554431||96666595865430||2880889.140{{0|000}}||4956372{{0|.000}}||1.7204||0.814351||59.52 ||35.76 
|-
|26||67108863||375619048086576||5597160.066{{0|000}}||9537863{{0|.000}}||1.7041||0.817384||60.49 ||36.73 
|}

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

:<math>A := -1 + \sum_{p\in\mathbb P} \frac{\ln p}{(p-1)^2} \approx 0.2269688 </math>

===Lower bounds===

For any sufficiently large number {{mvar | N}} and for any {{math | Δ ≥ (ln ln ''N'')<sup>3</sup>}}, 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''<sup>−Δ</sup>}}.<ref>Theorem 5 in Friedlander (2001)</ref>

===Minimal order===
For any sequence {{math | ''n''<sub>1</sub> < ''n''<sub>2</sub> < ''n''<sub>3</sub> < ⋯}} 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'')<sup>''c'' ln ln ln ''A''</sup>}}.<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
:<math>\eta=1-\frac{1+\ln\ln2}{\ln2} \approx 0.08607</math>

==Use in cryptography==

The Carmichael function is important in [[Cryptography|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''<sup>''r''</sup>}}, {{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''<sup>''r''</sup>}}. 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''<sub>2</sub>}} for some integer {{math | ''h''<sub>2</sub>}}. 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''<sub>1</sub> < ''p''<sub>2</sub> < ... < ''p<sub>k</sub>''}} are primes and {{math | ''r''<sub>1</sub>, ''r''<sub>2</sub>, ..., ''r<sub>k</sub>''}} 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==
* [[Carmichael number]]

==Notes==
<references/>

==References==
* {{cite journal |first1=Paul |last1= Erdős |first2=Carl |last2=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 |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]]

{{Sourceattribution|Carmichael function}}