# Carmichael function

Carmichael λ function : λ(n) for 1 ≤ n ≤ 1000 (compared to Euler φ function)

In number theory, the Carmichael function associates to every positive integer n a positive integer ${\displaystyle \lambda (n)}$, defined as the smallest positive integer m such that

${\displaystyle a^{m}\equiv 1{\pmod {n}}}$ for every integer a between 1 and n that is coprime to n.

(Dropping the phrase "between 1 and n" leads to an equivalent definition.) In algebraic terms, ${\displaystyle \lambda (n)}$ equals the exponent of the multiplicative group of integers modulo n.

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 first 36 values of ${\displaystyle \lambda (n)}$ (sequence A002322 in the OEIS) compared to Euler's totient function ${\displaystyle \varphi }$. (in bold if they are different, the ns such that they are different are listed in )

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 27 28 29 30 31 32 33 34 35 36
${\displaystyle \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 18 6 28 4 30 8 10 16 12 6
${\displaystyle \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 18 12 28 8 30 16 20 16 24 12

## Numerical example

Carmichael's function at 8 is 2, i.e. ${\displaystyle \lambda (8)=2}$, because for any number a co-prime to 8 it holds that a2 ≡ 1 (mod 8). Namely, 12 = 1 (mod 8), 32 = 9 ≡ 1 (mod 8), 52 = 25 ≡ 1 (mod 8) and 72 = 49 ≡ 1 (mod 8). Euler's totient function at 8 is 4, i.e. ${\displaystyle \varphi (8)=4}$, because there are 4 numbers lesser than and coprime to 8 (1, 3, 5, and 7). Euler's theorem assures that a4 ≡ 1 (mod 8) for all a coprime to 8, but 4 is not the smallest such exponent.

## Computing ${\displaystyle \lambda (n)}$ with Carmichael's theorem

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

${\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\dots p_{k}^{r_{k}}}$

where p1 < p2 < ... < pk are primes and r1 , ..., rk are positive integers. It is then the case that λ(n) is the least common multiple of the λ of each of its prime power factors:

${\displaystyle \lambda (n)=\operatorname {lcm} {\big (}\lambda (p_{1}^{r_{1}}),\,\lambda (p_{2}^{r_{2}}),\,\ldots ,\,\lambda (p_{k}^{r_{k}}){\big )}.}$

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, λ(n) is equal to the Euler totient φ(n); for powers of 2 greater than 4 it is equal to half of the Euler totient.

${\displaystyle \lambda (n)={\begin{cases}\;\;\varphi (n)&{\mbox{if }}n=2,3,4,5,6,7,9,10,11,13,14,17,18,19,22,23,25,26,27,29,31,34,\dots \\{\tfrac {1}{2}}\varphi (n)&{\text{if }}n=8,16,32,64,128,256,\dots \end{cases}}}$

Euler's function for prime powers is given by

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

## Properties of the Carmichael function

### Extension for powers of two

For a coprime to powers of 2 we have ${\displaystyle a=1+2h}$. Then,

${\displaystyle a^{2}=1+4h(h+1)=1+8C_{h+1}^{2}}$

where we take advantage of the fact that ${\displaystyle C_{h+1}^{2}={(h+1)h}/2}$ is an integer.

So, for k = 3, h an integer:

${\displaystyle a^{2^{k-2}}=1+2^{k}h}$
${\displaystyle a^{2^{k-1}}=(1+2^{k}h)^{2}=1+2^{k+1}(h+2^{k-1}h^{2})}$

By induction, when k ≥ 3, we have ${\displaystyle a^{2^{k-2}}\equiv 1{\pmod {2^{k}}}}$.

It provides that ${\displaystyle \lambda (2^{k})}$ is at most ${\displaystyle 2^{k-2}}$. [1]

### λ(n) divides φ(n)

This follows from elementary group theory, because the exponent of any finite abelian group must divide the order of the group. λ(n) is the exponent of the multiplicative group of integers modulo n while φ(n) is the order of that group.

We can thus view Carmichael's theorem as a sharpening of Euler's theorem.

### Minimality

Suppose ${\displaystyle a^{m}\equiv 1{\pmod {n}}}$ for all numbers a coprime with n. Then ${\displaystyle \lambda (n)|m}$.

Proof. If ${\displaystyle m=k\;\lambda (n)+r}$ with ${\displaystyle 0\leq r<\lambda (n)}$, then ${\displaystyle a^{r}=1^{k}\cdot a^{r}\equiv (a^{\lambda (n)})^{k}\cdot a^{r}=a^{k\;\lambda (n)+r}=a^{m}\equiv 1{\pmod {n}}}$ for all numbers a coprime with n. It follows ${\displaystyle r=0}$ , since ${\displaystyle r<\lambda (n)}$ and ${\displaystyle \lambda (n)}$ the minimal positive such number.

### Divisibility

${\displaystyle a|b\Rightarrow \lambda (a)|\lambda (b)}$

Proof. The result follows from the formula

${\displaystyle \lambda (n)=\operatorname {lcm} {\big (}\lambda (p_{1}^{r_{1}}),\,\lambda (p_{2}^{r_{2}}),\,\ldots ,\,\lambda (p_{k}^{r_{k}}){\big )}}$

mentioned above.

### Composition

For all positive integers ${\displaystyle a}$ and ${\displaystyle b}$ it holds

${\displaystyle \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 ${\displaystyle a}$ and ${\displaystyle n}$ be coprime and let ${\displaystyle m}$ be the smallest exponent with ${\displaystyle a^{m}\equiv 1{\pmod {n}}}$, then it holds

${\displaystyle m|\lambda (n)}$ .

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

### Exponential cycle length

If ${\displaystyle n}$ has maximum prime exponent ${\displaystyle r_{\rm {max}}}$ under prime factorization, then for all ${\displaystyle a}$ (including those not co-prime to ${\displaystyle n}$) and all ${\displaystyle r\geq r_{\rm {max}}}$,

${\displaystyle a^{r}\equiv a^{r+\lambda (n)}{\pmod {n}}}$

In particular, for squarefree ${\displaystyle n}$ (${\displaystyle r_{\rm {max}}=1}$), for all ${\displaystyle a}$

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

### Average and typical value

For any x > 16:

${\displaystyle {\frac {1}{x}}\sum _{n\leq x}\lambda (n)={\frac {x}{\ln x}}e^{B(1+o(1))\ln \ln x/(\ln \ln \ln x)}}$.[2][3]

Where B is a constant,

${\displaystyle B=e^{-\gamma }\prod _{p}\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537\ .}$

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

${\displaystyle \lambda (n)=n/(\ln n)^{\ln \ln \ln n+A+o(1)}\,}$

where A is a constant,[3][4]

${\displaystyle A=-1+\sum _{p}{\frac {\log p}{(p-1)^{2}}}\approx 0.2269688\ .}$

### Lower bounds

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

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

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

For any sequence ${\displaystyle n_{1} of positive integers, any constant ${\displaystyle 0, and any sufficiently large i:

${\displaystyle \lambda (n_{i})>(\ln n_{i})^{c\ln \ln \ln n_{i}}}$.[6][7]

### Small values

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

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

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

### Image of the function

The set of values of the Carmichael function has counting function

${\displaystyle {\frac {x}{(\log x)^{\eta +o(1)}}}\ ,}$

where ${\displaystyle \eta =1-{\frac {1+\log \log 2}{\log 2}}=0.08607}$….[8]

## Use in cryptography

The Carmichael function is important in cryptography due its use in the RSA encryption algorithm.