Carmichael function

Carmichael function
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 .
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 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 examples
Carmichael's function at 5 is 4 because for any number coprime to 5, i.e. there is with namely , and . And this is the smallest exponent with this property, because (and as well.)Moreover, Euler's totient function at 5 is 4 because there are exactly 4 numbers less than and coprime to 5 (1, 2, 3, and 4). Euler's theorem assures that for all coprime to 5, and 4 is the smallest such exponent.
Carmichael's function at 8 is 2 because for any number coprime to 8, i.e. it holds that . Namely , and .Euler's totient function at 8 is 4 because there are exactly 4 numbers less than and coprime to 8 (1, 3, 5, and 7). Moreover, 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 with (and thus also ), 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 is the biggest exponent in the prime factorization of , 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