# Carmichael function

In number theory, the **Carmichael function** of a positive integer *n*, denoted , is defined as the smallest positive integer *m* such that

for every integer *a* that is coprime to *n*. In other words, in more algebraic terms, it defines the exponent of the multiplicative group of integers modulo n. The Carmichael function is also known as the **reduced totient function** or the **least universal exponent function**, and is sometimes also denoted .

The first 36 values of (sequence A002322 in OEIS) compared to Euler's totient function . (in **bold** if they are different)

## Numeric example

7^{2} = 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^{4 }= 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 equals 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. ^{[1]}

## 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 4 it is equal to one 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*_{1} < *p*_{2} < ... < *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.

## Hierarchy of results

Since λ(*n*) divides φ(*n*), Euler's totient function (the quotients are listed in Template:Oeis), 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.

## Properties of the Carmichael function

### Divisibility

### Composition

For all positive integers and it holds

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

### Primitive m-th roots of unity

Let and be coprime and let be the smallest exponent with , then it holds

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

### Exponential cycle length

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

In particular, for squarefree (), for all

### Average and typical value

For any *x* > 16, and a constant *B*:

Here

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

where *A* is a constant,^{[3]}^{[4]}

### Lower bounds

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

positive integers such that .^{[5]}

For any sequence of positive integers, any constant , and any sufficiently large *i*:

### Small values

For a constant *c* and any sufficiently large positive *A*, there exists an integer such that .^{[7]}
Moreover, *n* is of the form

for some square-free integer .^{[6]}

### Image of the function

The set of values of the Carmichael function has counting function

where η=1−(1+loglog2)/(log2)=0.08607….^{[8]}

## See also

## Notes

- ↑ http://www25.brinkster.com/denshade/totient.html
- ↑ Theorem 3 in Erdös (1991)
- ↑
^{3.0}^{3.1}Sándor & Crstici (2004) p.194 - ↑ Theorem 2 in Erdös (1991)
- ↑ Theorem 5 in Friedlander (2001)
- ↑
^{6.0}^{6.1}Theorem 1 in Erdös 1991 - ↑
^{7.0}^{7.1}Sándor & Crstici (2004) p.193 - ↑ Template:Cite arxiv

## References

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

{{#invoke: Navbox | navbox }}