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

\[ \begin{align} \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} \, \left(\lambda\left({p_1}^{\alpha_1}\right), \cdots, \lambda\left({p_k}^{\alpha_k}\right)\right), \end{align} \] where the \( p_i \) are distinct positive prime numbers.

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

(1) If \( a|b,\) then \( \lambda(a)|\lambda(b).\)

(2) \( \lambda(\text{lcm}(a,b)) = \text{lcm}(\lambda(a),\lambda(b)).\)

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

\( \lambda(360) = \text{lcm}(\lambda(2^3),\lambda(3^2),\lambda(5)) = \text{lcm}(2,6,4) = 12. \)

Note in this example that \( 360|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})|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}\) (and \( g_i=5\) if \( p_i^{\alpha_i}\) is a power of 2 greater than 4), 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.

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}(\lambda(2^4),\lambda(3^2),\lambda(5)) = \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{align} x &\equiv 5 \pmod{2^4} \\ x &\equiv 5 \pmod{3^2} \\ x &\equiv 3 \pmod{5} \end{align} \] to get the solution \( x \equiv 293 \pmod{720}.\) This is not unique (exercise: how many different primitive lambda-roots are there?).

## 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 \) (and \( \text{gcd}(a,n)=1)\), 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)|(n-1),\) say \( \lambda(n)k = n-1,\) then \( a^{n-1} \equiv (a^{\lambda(n)})^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)|(n-1).\)

\( \lambda(561) = \text{lcm}(\lambda(3),\lambda(11),\lambda(17))=\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/