Carmichael function
In number theory, a branch of mathematics, the Carmichael function  of a positive integer  is the smallest positive integer  such that

for every integer  between 1 and  that is coprime to . In algebraic terms,  is the exponent of the multiplicative group of integers modulo .

The Carmichael function is named after the American mathematician Robert Carmichael and 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   with Euler's totient function  (in bold if they are different; the s such that they are different are listed in ).

Numerical example
Carmichael's function at 8 is 2, , because for any number  coprime to 8 it holds that . Namely, ,  ,  and . Euler's totient function at 8 is 4, , because there are 4 numbers less than and coprime to 8 (1, 3, 5, and 7).  Euler's theorem assures that  for all  coprime to 8, but 4 is not the smallest such exponent.

Computing  with Carmichael's theorem 

By the unique factorization theorem, any  can be written in a unique way as

where  are primes and  are positive integers. Then  is the least common multiple of the  of each of its prime power factors:

This can be proved using the Chinese remainder theorem.

Carmichael's theorem explains how to compute  of a prime power : for a power of an odd prime and for 2 and 4,  is equal to the Euler totient ; for powers of 2 greater than 4 it is equal to half of the Euler totient:

Euler's function for prime powers  is given by

Properties of the Carmichael function
In this section, an integer  is divisible by a nonzero integer  if there exists an integer  such that . This is written as

Order of elements modulo 
Let  and  be coprime and let  be the smallest exponent with , then it holds that
.
That is, the order  of a unit  in the ring of integers modulo  divides  and

Minimality

Suppose  for all numbers  coprime with . Then .

Proof: If  with , then 

for all numbers  coprime with . It follows , since  and  the minimal positive such number.

divides  
This follows from elementary group theory, because the exponent of any finite group must divide the order of the group.  is the exponent of the multiplicative group of integers modulo  while  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.

Divisibility

Proof.

By definition, for any integer , we have that  , and therefore . By the minimality property above, we have .

Composition

For all positive integers  and  it holds that
.
This is an immediate consequence of the recursive definition of the Carmichael function.

Exponential cycle length

If  has maximum prime exponent  under prime factorization, then for all  (including those not coprime to ) and all ,

In particular, for square-free  (), for all  we have

Extension for powers of two
For  coprime to (powers of) 2 we have  for some . Then,
	

 
where we take advantage of the fact that  is an integer.
 
So, for ,  an integer:

By induction, when , we have

It provides that  is at most .

Average value

For any :

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

and , the Euler–Mascheroni constant.

The following table gives some overview over the first  values of the  function, for both, the exact average and its Erdős-approximation.

Additionally given is some overview over the more easily accessible    with
 .
There, the table entry in row number 26 at column
   → 60.49
indicates that 60.49% (≈ ) of the integers  have  meaning that the majority of the  values is exponential in the length  of the input , namely

{| class="wikitable" style="text-align:right"
|- style="vertical-align:top"
!  ||  || sum || average || Erdős average || Erdős /exact average ||  average || %  >  || %  > 
|-
|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||1.9422||0.781064||49.13 ||28.17 
|-
|17||131071||1964413592||14987.40066||28576.97||1.9067||0.785401||50.43 ||29.55 
|-
|18||262143||7529218208||28721.79768||53869.76||1.8756||0.789561||51.17 ||30.67 
|-
|19||524287||28935644342||55190.46694||101930.9||1.8469||0.793536||52.62 ||31.45 
|-
|20||1048575||111393101150||106232.8409||193507.1||1.8215||0.797351||53.74 ||31.83 
|-
|21||2097151||429685077652||204889.9090||368427.6||1.7982||0.801018||54.97 ||32.18 
|-
|22||4194303||1660388309120||395867.5158||703289.4||1.7766||0.804543||56.24 ||33.65 
|-
|23||8388607||6425917227352||766029.1187||1345633||1.7566||0.807936||57.19 ||34.32 
|-
|24||16777215||24906872655990||1484565.386||2580070||1.7379||0.811204||58.49 ||34.43 
|-
|25||33554431||96666595865430||2880889.140||4956372||1.7204||0.814351||59.52 ||35.76 
|-
|26||67108863||375619048086576||5597160.066||9537863||1.7041||0.817384||60.49 ||36.73 
|}

Prevailing interval
For all numbers  and all but  positive integers  (a "prevailing" majority):

with the constant

Lower bounds

For any sufficiently large number  and for any , there are at most

positive integers  such that .

Minimal order
For any sequence  of positive integers, any constant , and any sufficiently large :

Small values

For a constant  and any sufficiently large positive , there exists an integer  such that

Moreover,  is of the form

for some square-free integer .

Image of the function
The set of values of the Carmichael function has counting function

where

Use in cryptography

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

See also
 Carmichael number

Notes

References
 
 
 
 

Modular arithmetic
Functions and mappings