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

holds for every integer coprime to . In algebraic terms, is the exponent of the multiplicative group of integers modulo n. As this is a finite abelian group, there must exist an element whose order equals the exponent, . Such an element is called a primitive -root modulo .

The Carmichael function is named after the American mathematician Robert Carmichael who defined it in 1910. 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 is , where is Euler's totient function. Since the order of an element of a finite group divides the order of the group, divides . The following table compares the first 36 values of and (in bold if they are different; the values of such that they are different are listed in ).

Numerical examples

• . The set of numbers less than and coprime to 5 is }. Hence Euler's totient function has value and the value of Carmichael's function, , must be a divisor. Hence . Both 2 and 3 are primitive -roots modulo 5 and also primitive roots modulo 5.

• . The set of numbers less than and coprime to 8 is . Hence and must be a divisor of 4. In fact . The primitive -roots modulo 8 are 3, 5, and 7. There are no primitive roots modulo 8.

Recurrence for λ(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 of the product is the least common multiple of the of the prime power factors. Specifically, is given by the recurrence

Euler's totient for a prime power, that is, a number with prime and , is given by

Carmichael's theorems

Carmichael proved two theorems that, together, establish that if 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 for all relatively prime to . This implies that the order of every element of the multiplicative group of integers modulo divides . Carmichael calls an element is the least power of congruent to 1 (mod ) a primitive λ-root modulo n. (This is not to be confused with a primitive root modulo n-root modulo .) If is one of the primitive has no positive integer solutions less than , showing that there is no positive for all relatively prime to .

The second statement of Theorem 2 does not imply that all primitive -roots modulo are congruent to powers of a single root . For example, if , then . There are four primitive ), 11, and 14, are not primitive -roots modulo 15.

For a contrasting example, if . There are two primitive -roots modulo 9.

Properties of the Carmichael function

In this section, an integer. This is written as

A consequence of minimality of λ(n)

Suppose for all numbers coprime with . Then .

Proof: If with , then

for all numbers coprime with . It follows that since and is the minimal positive exponent for which the congruence holds for all coprime with .

λ(n) divides φ(n)

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.

for all relatively prime to .

Composition

For all positive integers and it holds that

1. .

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

Exponential cycle length

of , then for all (including those not coprime to ) and all ,

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

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

1. {| 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.

Proof of Theorem 1

For , a prime, Theorem 1 is equivalent to Fermat's little theorem:

For prime powers , , if

holds for some integer , then raising both sides to the power gives

for all relatively prime to and hence to . This establishes the theorem for or any odd prime power.

Sharpening the result for higher powers of two

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

1. ,

is an integer. With , this is written

Squaring both sides gives

is an integer. It follows by induction that

and all .

Integers with multiple prime factors

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

where are primes and ,

From this it follows that

where, as given by the recurrence,

From the Chinese remainder theorem one concludes that

See also

• Carmichael number

Notes

References