Carmichael function


In number theory, a branch of mathematics, the Carmichael function associates to every positive integer a positive integer, defined as 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 the reduced totient function or the least universal exponent function.
The following table compares the first 36 values of with Euler's totient function .
123456789101112131415161718192021222324252627282930313233343536
11224262641021264416618461022220121862843081016126
112242646410412688166188121022820121812288301620162412

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

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.

Extension for powers of two

For coprime to 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.

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.
We can thus view Carmichael's theorem as a sharpening of Euler's theorem.

Divisibility

Proof. The result follows from the formula
mentioned above.

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 and all,
In particular, for square-free , for all we have

Average value

For any :
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
indicates that 60.49% of the integers have meaning that the majority of the values is exponential in the length of the input, namely

Prevailing interval

For all numbers and all but positive integers :
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 its use in the RSA encryption algorithm.