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.

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.\)

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

We have

\[\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} \, \big(\lambda\left({p_1}^{\alpha_1}\right), \cdots, \lambda\left({p_k}^{\alpha_k}\right)\big), \end{align}\]

where the \( p_i \) are distinct positive prime numbers.

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

1. If \( a|b,\) then \( \lambda(a)|\lambda(b).\)
2. \( \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.

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{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?). \(_\square\)

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.