# Carmichael function

(Redirected from Carmichael's totient 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 {\color {Blue}a^{m}\equiv 1{\pmod {n}}}}$ for every integer a between 1 and n that is coprime to n.

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 unique factorization theorem, 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, r2, ..., rk are positive integers. Then λ(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 pr: for a power of an odd prime and for 2 and 4, λ(pr) is equal to the Euler totient φ(pr); for powers of 2 greater than 4 it is equal to half of the Euler totient:

${\displaystyle \lambda (p^{r})={\begin{cases}\;\;\varphi (p^{r})&{\mbox{if }}p^{r}=2,3,4,5,7,9,11,13,17,19,23,25,27,29,31,\dots \\{\tfrac {1}{2}}\varphi (p^{r})&{\text{if }}p^{r}=8,16,32,64,128,256,\dots \end{cases}}}$

Euler's function for prime powers pr is given by

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

## Properties of the Carmichael function

### Order of elements modulo n

Let a and n be coprime and let m be the smallest exponent with ${\displaystyle a^{m}\equiv 1{\pmod {n}}}$, then it holds

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

That is, the order m := ordn(a) of a unit a in the ring of integers modulo n divides ${\displaystyle \lambda (n)}$ and

${\displaystyle \lambda (n)=\max\{\operatorname {ord} _{n}(a)\,\colon \,\gcd(a,n)=1\}}$

### 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 r = 0, since ${\displaystyle r<\lambda (n)}$ and ${\displaystyle \lambda (n)}$ the minimal positive such number.

### 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}$

where we take advantage of the fact that ${\displaystyle C:={(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.

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

### 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 value

For any n ≥ 16:

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

(called Erdős-approximation in the sequel) with the constant

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

and ${\displaystyle \gamma \approx 0.57721}$, the Euler–Mascheroni constant.

The following table gives some overview over the first 226–1 = 67108863 values of the λ-function, for both, the exact average and its Erdős-approximation.

Additionally given is some overview over the more easily accessible “Logarithm over Logarithm”-values LoL(n) := ln λ(n)ln n with

• LoL(n) > 4/5         ${\displaystyle \Longleftrightarrow \quad \lambda (n)>n^{4/5}}$ .

There, the table entry in row number 26 at column

•  % LoL > 4/5         ${\displaystyle \longrightarrow }$       60.49

indicates that 60.49 % (≈ 40,000,000) of the numbers ${\displaystyle n\in \{1,\ldots ,67108863\}}$ have ${\displaystyle \lambda (n)>n^{4/5}}$ meaning that the majority of the λ-values is exponential in the length ${\displaystyle l:=\log _{2}(n)}$ of the input ${\displaystyle n}$ , namely ${\displaystyle {\biggl (}2^{\tfrac {4}{5}}{\biggr )}^{l}=2^{\tfrac {4\,l}{5}}={\bigl (}2^{l}{\bigr )}^{\tfrac {4}{5}}=n^{\tfrac {4}{5}}}$ .

 ν n = 2ν–1 sum${\displaystyle \sum _{i\leq n}\lambda (i)}$ average${\displaystyle {\tfrac {1}{n}}\sum _{i\leq n}\lambda (i)}$ Erdős-average Erdős / exact-average LoL-average % LoL > 4/5 % LoL > 7/8 5 31 270 8.709677 68.643 7.8813 0.678244 41.94 35.48 6 63 964 15.301587 61.414 4.0136 0.699891 38.10 30.16 7 127 3574 28.141732 86.605 3.0774 0.717291 38.58 27.56 8 255 12994 50.956863 138.190 2.7119 0.730331 38.82 23.53 9 511 48032 93.996086 233.149 2.4804 0.740498 40.90 25.05 10 1023 178816 174.795699 406.145 2.3235 0.748482 41.45 26.98 11 2047 662952 323.865169 722.526 2.2309 0.754886 42.84 27.70 12 4095 2490948 608.290110 1304.810 2.1450 0.761027 43.74 28.11 13 8191 9382764 1145.496765 2383.263 2.0806 0.766571 44.33 28.60 14 16383 35504586 2167.160227 4392.129 2.0267 0.771695 46.10 29.52 15 32767 134736824 4111.967040 8153.054 1.9828 0.776437 47.21 29.15 16 65535 513758796 7839.456718 15225.43 1.9422 0.781064 49.13 28.17 17 131071 1964413592 14987.40066 28576.97 1.9067 0.785401 50.43 29.55 18 262143 7529218208 28721.79768 53869.76 1.8756 0.789561 51.17 30.67 19 524287 28935644342 55190.46694 101930.9 1.8469 0.793536 52.62 31.45 20 1048575 111393101150 106232.8409 193507.1 1.8215 0.797351 53.74 31.83 21 2097151 429685077652 204889.9090 368427.6 1.7982 0.801018 54.97 32.18 22 4194303 1660388309120 395867.5158 703289.4 1.7766 0.804543 56.24 33.65 23 8388607 6425917227352 766029.1187 1345633 1.7566 0.807936 57.19 34.32 24 16777215 24906872655990 1484565.386 2580070 1.7379 0.811204 58.49 34.43 25 33554431 96666595865430 2880889.140 4956372 1.7204 0.814351 59.52 35.76 26 67108863 375619048086576 5597160.066 9537863 1.7041 0.817384 60.49 36.73

### Prevailing interval

For all numbers N and all but o(N)[4] positive integers nN (a «prevailing» majority):

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

with the constant[3]

${\displaystyle A:=-1+\sum _{p\in \mathbb {P} }{\frac {\ln 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]

### Minimal order

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.