Carmichael function

In number theory, the Carmichael function of a positive integer n, denoted $\lambda(n)$ , is defined as the smallest positive integer m such that

$a^m \equiv 1 \pmod{n}$

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 $\psi(n)$ .

The first 26 values of $\lambda$ (sequence A002322 in OEIS) compared to Euler's totient function $\varphi$ :

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26
$\lambda(n)$	1	1	2	2	4	2	6	2	6	4	10	2	12	6	4	4	16	6	18	4	6	10	22	2	20	12
$\varphi(n)$	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	12	10	22	8	20	12

1 Numeric example
2 Carmichael's theorem
3 Hierarchy of results
4 Properties of the Carmichael function
5 See also
6 Notes
7 References

Numeric example

5² ≡ 1 (mod 6) because 5 and 6 are coprime. In other words, gcd(5,6)=1. Here we had to raise 5 to the 2nd power because the Carmichael function of 6 is 2.^[1] Recall that 1 and 5 are the only two numbers smaller than 6 that are relatively prime to 6.

However, 3² = 9 ≡ 3 (mod 6) obviously doesn't work because the number 3 is impermissible as a base to be raised to the 2nd power. We know that gcd(3,6)=3, not 1.

Carmichael's theorem

For powers of odd primes 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:

$\lambda(n) = \begin{cases} \;\;\phi(n) &\mbox{if }n = 2,3,4,5,7,9,11,13,17,19,23,25,27,\dots\\ \tfrac12\phi(n)&\text{if }n=8,16,32,64,\dots \end{cases}$

Euler's function for prime powers is given by

$\varphi(p^k) = p^{k-1}(p-1).\;$

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

$n= p_1^{a_1}p_2^{a_2} \dots p_{\omega(n)}^{a_{\omega(n)}}$

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:

$\lambda(n) = \operatorname{lcm}[\lambda(p_1^{a_1}),\;\lambda(p_2^{a_2}),\dots,\lambda(p_{\omega(n)}^{a_{\omega(n)}}) ].$

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

$a^{\lambda(n)} \equiv 1 \pmod{n},$

where $\lambda$ 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

The classical Euler's theorem implies that λ(n) divides φ(n), Euler's totient function. In fact 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 adds nothing to Fermat's theorem, 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

$a|b \implies \lambda(a)|\lambda(b)$

Composition

For all positive integers $a$ and $b$ it holds

$\lambda(\mathrm{lcm}(a,b)) = \mathrm{lcm}( \lambda(a), \lambda(b) )$ .

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 \equiv 1 \pmod{n}$ , then it holds

$m | \lambda(n)$ .

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

Average and typical value

For any x > 16, and a constant B ≈ 0.34537:

$\frac{1}{x} \sum_{n \leq x} \lambda (n) = \frac{x}{\ln x} e^{B(\ln\ln x) (1%2Bo(1)) / (\ln\ln\ln x) }$ .^[2]

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

$\lambda(n) = n / (\ln n)^{\ln\ln\ln n %2B A %2B o(1)}\,$

where A is a constant, A ≈ 0.226969.^[3]

Lower bounds

For any sufficiently large number N and for any $\Delta \geq (\ln\ln N)^3$ , there are at most

$Ne^{-0.69(\Delta\ln\Delta)^{1/3}}$

positive integers $n \leq N$ such that $\lambda(n) \leq ne^{-\Delta}$ .^[4]

For any sequence $n_1<n_2<n_3<\cdots$ of positive integers, any constant $0<c<1/\ln2$ , and any sufficiently large i:

$\lambda(n_i) > (\ln n_i)^{c\ln\ln\ln n_i}$ .^[5]

Small values

For a constant c and any sufficiently large positive A, there exists an integer $n>A$ such that $\lambda(n)<(\ln A)^{c\ln\ln\ln A}$ . Moreover, n is of the form

$n=\prod_{(q-1)|m \text{ and } q \text{ is prime}}q$

for some square-free integer $m<(\ln A)^{c\ln\ln\ln A}$ .^[6]

Notes

^ http://www25.brinkster.com/denshade/totient.html
^ Theorem 3 in Erdös (1991)
^ Theorem 2 in Erdös (1991)
^ Theorem 5 in Friedlander (2001)
^ Theorem 1 in Erdös 1991
^ Theorem 1 in Erdös 1991

References

Erdős, Paul; Pomerance, Carl; Schmutz, Eric (1991). "Carmichael's lambda function". Acta Arithmetica 58: 363–385. MR 1121092.

Friedlander, John; Pomerance, Carl; Shparlinski, Igor E. (2001). "Period of the power generator and small values of the Carmichael function". Mathematics of Computation 70 (236): 1591–1605. MR 1836921.