# Carmichael's Lambda Function

**Carmichael's lambda function** is the reduced totient function. It is the smallest positive divisor of Euler's totient function that satisfies the conclusion of Euler's theorem. It is used in primality testing.

#### Contents

## Definition

Let $n$ be a positive integer. Then $\lambda(n)$ is defined to be the smallest positive integer $k$ such that $a^k \equiv 1 \pmod n$ for all $a$ such that $\text{gcd}(a,n)=1.$

Note that $\lambda(n)$ always exists because $k= \phi(n)$ satisfies the equation above, by Euler's theorem. So $\lambda(n) \le \phi(n).$ In fact, $\lambda(n)|\phi(n),$ by a standard division algorithm argument: let $\phi(n) = \lambda(n) q+r,$ $0 \le r < \lambda(n);$ then it's clear that $a^r \equiv 1 \pmod n$ for all $a$ coprime to $n.$ This contradicts minimality of $\lambda(n)$ unless $r=0.$

## Computing Carmichael's Function

Values of Carmichael's lambda function can be calculated using the following formulas:

We have

$\begin{aligned} \lambda\left(p^{\alpha}\right) &= \begin{cases} \phi\left(p^{\alpha}\right) &\text{ if } \alpha \leq 2 \text{ or } p \geq 3 \\ \frac{1}{2} \phi\left(p^{\alpha}\right) &\text{ if } \alpha \geq 3 \text{ and } p = 2 \end{cases} \\\\ \lambda\left( {p_1}^{\alpha_1} \cdots {p_k}^{\alpha_k} \right) &= \text{lcm} \, \big(\lambda\left({p_1}^{\alpha_1}\right), \cdots, \lambda\left({p_k}^{\alpha_k}\right)\big), \end{aligned}$

where the $p_i$ are distinct positive prime numbers.

These formulas will be proved in the next section. Two immediate consequences are as follows:

- If $a|b,$ then $\lambda(a)|\lambda(b).$
- $\lambda\big(\text{lcm}(a,b)\big) = \text{lcm}\big(\lambda(a),\lambda(b)\big).$

Find the smallest positive integer $a$ such that $360|(x^a-1)$ for any $x$ relatively prime to $360.$

We have $\lambda(360) = \text{lcm}\big(\lambda(2^3),\lambda(3^2),\lambda(5)\big) = \text{lcm}(2,6,4) = 12.$ $_\square$

Note in this example that $360\Big|x^3(x^{12}-1)$ for all $x,$ since $2^3,3^2,5$ all either divide $x^3$ or $x^{12}-1$ depending on whether $x$ is divisible by $2,3,5$ respectively.

## Proof of the Formulas

Let $p$ be an odd prime. An element of order $\phi(p^\alpha)$ in $\left( {\mathbb Z}/p^\alpha{\mathbb Z} \right)^*$ is called a primitive root. The wiki on primitive roots contains the full classification of integers $n$ for which there is a primitive root mod $n;$ in particular, there is a primitive root $g$ mod $n$ when $n$ is an odd prime power. Since the smallest positive integer power of $g$ that is congruent to $1$ is $g^{\phi(p^{\alpha})},$ this shows that $\lambda(p^{\alpha}) \ge \phi(p^\alpha).$ Since $\lambda(p^{\alpha}) \le \phi(p^{\alpha})$ from the discussion in the previous section, this shows that they are equal.

When $p=2,$ the primitive roots wiki shows that $\lambda(2^{\alpha})\big|2^{\alpha-2}$ for $\alpha \ge 3,$ and an easy induction shows that $5^{2^{\alpha-3}} \equiv 1 + 2^{\alpha-1} \pmod {2^{\alpha}},$ so the order of $5$ does not divide $2^{\alpha-3},$ but it is a power of 2, so it is $2^{\alpha-2}.$ This shows that $\lambda(2^{\alpha}) = 2^{\alpha-2} = \frac12 \phi(2^{\alpha}).$

The last statement is a straightforward application of the Chinese remainder theorem. In particular, if $n = p_1^{\alpha_1}\cdots p_k^{\alpha_k},$ then for any choice of primitive roots $g_i \mod p_i^{\alpha_i}$ $\big($and $g_i=5$ if $p_i^{\alpha_i}$ is a power of 2 greater than 4$\big),$ there is a unique element $g$ mod $n$ that is congruent to each of the $g_i$ mod $p_i^{\alpha_i},$ and it is easy to show that the order of $g$ equals the LCM of the $\lambda(p_i^{\alpha_i}).$ On the other hand, a similar Chinese remainder theorem argument shows that any element raised to that LCM must be $1$ mod $n$ since it is $1$ modulo all the prime powers. $_\square$

One important fact that is immediate from the proof is **there is always an element $g \in ({\mathbb Z}/n{\mathbb Z})^*$ whose multiplicative order equals $\lambda(n).$** Such $g$ are sometimes called **primitive lambda-roots**.

Find a primitive lambda-root modulo $720.$

Start with $\lambda(144) = \text{lcm}\big(\lambda(2^4),\lambda(3^2),\lambda(5)\big) = \text{lcm}(4,6,4) = 12.$ The idea is to find primitive lambda-roots modulo $2^4,$ $3^2,$ and $5,$ and apply the Chinese remainder theorem. $5$ always works modulo powers of $2,$ and $5$ is actually a primitive root modulo $3^2$ as well. For a primitive root mod $5,$ $3$ will suffice. So now solve $\begin{aligned} x &\equiv 5 \pmod{2^4} \\ x &\equiv 5 \pmod{3^2} \\ x &\equiv 3 \pmod{5} \end{aligned}$ to get the solution $x \equiv 293 \pmod{720}.$ This is not unique (exercise: how many different primitive lambda-roots are there?). $_\square$

## Application to Primality Testing

Since Fermat's little theorem implies that $a^{p-1} \equiv 1 \pmod p$ for all positive integers $a$ less than a given prime $p,$ a natural test for primality is as follows: given a large number $n,$ pick an integer $a<n$ and compute $a^{n-1} \pmod n.$ If the answer is not $1,$ then $n$ is not prime.

But if $a^{n-1} \equiv 1 \pmod n$ $\big($and $\text{gcd}(a,n)=1\big),$ is it possible to say that $n$ is prime? The answer is no; for instance, $2^{340} \equiv 1 \pmod {341},$ but $341 = 11\cdot 31.$ On the other hand, $3^{340} \equiv 56 \not\equiv 1 \pmod {341},$ so varying the choice of $a$ takes care of $341.$

Unfortunately, there are some composite values of $n$ for which any choice of $a$ relatively prime to $n$ will result in an inconclusive test. If $\lambda(n)\big|(n-1),$ say $\lambda(n)k = n-1,$ then $a^{n-1} \equiv \big(a^{\lambda(n)}\big)^k \equiv 1 \pmod n,$ so no choice of $a$ will show that $n$ is composite. A composite number $n$ which cannot be proved composite by this primality test is called a **Carmichael number**. By a division algorithm argument (similar to the one given earlier in this wiki), the converse of this criterion is true as well: $n$ is a Carmichael number if and only if $\lambda(n)\big|(n-1).$

$\lambda(561) = \text{lcm}\big(\lambda(3),\lambda(11),\lambda(17)\big)=\text{lcm}(2,10,16) = 80,$ which divides $560.$ So $561$ is a Carmichael number (in fact, it is the smallest Carmichael number).

See the Carmichael numbers wiki for more details.

**Cite as:**Carmichael's Lambda Function.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/carmichaels-lambda-function/