Carmichael function

Numerical example

7² = 49 ≡ 1 (mod 8) because 7 and 8 are coprime (their greatest common divisor equals 1; they have no common factors) and the value of Carmichael's function at 8 is 2. Euler's totient function is 4 at 8 because there are 4 numbers lesser than and coprime to 8 (1, 3, 5, and 7). Whilst it is true that 7⁴ = 2401 ≡ 1 (mod 8), as shown by Euler's theorem, raising 7 to the fourth power is unnecessary because the Carmichael function indicates that 7 squared is congruent to 1 (mod 8). Raising 7 to exponents greater than 2 only repeats the cycle 7, 1, 7, 1, ... . Because the same holds true for 3 and 5, the Carmichael number is 2 rather than 4.

Carmichael's theorem

For a power of an odd prime, twice the power of an odd prime, and for 2 and 4, λ(n) is equal to the Euler totient φ(n); for powers of 2 greater than 2 it is equal to half of the Euler totient:

Euler's function for prime powers is given by

By the fundamental theorem of arithmetic any n > 1 can be written in a unique way

where p₁ < p₂ < ... < p_ω are primes and the a_i > 0. (n = 1 corresponds to the empty product.)

For general n, λ(n) is the least common multiple of λ of each of its prime power factors:

Carmichael's theorem states that if a is coprime to n, then

where λ is the Carmichael function defined above. In other words, it asserts the correctness of the formulas. This can be proven by considering any primitive root modulo n and the Chinese remainder theorem.

Proofs

The following proofs proceed by induction.

Proof for Odd Prime Powers

From Fermat's little theorem, we have a p − 1 = 1 + h p . For k = 1, h an integer:

for some integer h₀.

By induction, we have a p k − 1 ( p − 1 ) ≡ 1 ( mod p k ) .

Proof for Powers of Two

For a coprime to powers of 2 we have a = 1 + 2 h . Then,

where we take advantage of the fact that C h + 1 2 = ( h + 1 ) h / 2 is an integer.

So, for k = 3, h an integer:

By induction, when k ≥ 3, we have a 2 k − 2 ≡ 1 ( mod 2 k ) .

Hierarchy of results

Since λ(n) divides φ(n), Euler's totient function (the quotients are listed in  A034380), the Carmichael function is a stronger result than the classical Euler's theorem. Clearly Carmichael's theorem is related to Euler's theorem, because the exponent of a finite abelian group must divide the order of the group, by elementary group theory. The two functions differ already in small cases: λ(15) = 4 while φ(15) = 8 (see  A033949 for the associated n).

Fermat's little theorem is the special case of Euler's theorem in which n is a prime number p. Carmichael's theorem for a prime p gives the same result, because the group in question is a cyclic group for which the order and exponent are both p − 1.

Divisibility

Composition

For all positive integers a and b it holds

This is an immediate consequence of the recursive definition of the Carmichael function.

Primitive m-th roots of unity

Let a and n be coprime and let m be the smallest exponent with a m ≡ 1 ( mod n ) , then it holds

That is, the orders of primitive roots of unity in the ring of integers modulo n are divisors of λ ( n ) .

Exponential cycle length

For a number n with maximum prime exponent of x m a x under prime factorization, then for all a (including those not co-prime to n ) and all k ≥ x m a x ,

In particular, for squarefree n ( x m a x = 1 ), for all a

Average and typical value

For any x > 16:

Where B is a constant,

For all numbers N and all except o(N) positive integers n ≤ N:

where A is a constant,

Lower bounds

For any sufficiently large number N and for any Δ ≥ ( ln ⁡ ln ⁡ N ) 3 , there are at most

positive integers n ≤ N such that λ ( n ) ≤ n e − Δ .

For any sequence n 1 < n 2 < n 3 < ⋯ of positive integers, any constant 0 < c < 1 / ln ⁡ 2 , and any sufficiently large i:

Small values

For a constant c and any sufficiently large positive A, there exists an integer n > A such that λ ( n ) < ( ln ⁡ A ) c ln ⁡ ln ⁡ ln ⁡ A . Moreover, n is of the form

for some square-free integer m < ( ln ⁡ A ) c ln ⁡ ln ⁡ ln ⁡ A .

Image of the function

The set of values of the Carmichael function has counting function

where η = 1 − 1 + log ⁡ log ⁡ 2 log ⁡ 2 = 0.08607 ….