### Regarding Carmichael's function

Those familiar with number theory will remember that Euler's totient function, usually called phi, counts the number of inversible elements modulo m. So for example, since phi(p) = p-1, it means that with the exception of zero, all the elements of Z/pZ are inversible.

Furthermore, it is interesting to consider the multiplicative subgroup of Z/mZ --- those elements of Z/mZ that are inversible. A very important question is whether this group is cyclic, which if true would mean there is an element g the powers of which generate the whole group.

Now, Fermat's little theorem states that if p is prime and a is not zero, a^{p-1} = 1 mod p. In other words, no matter the a, raising it to the power of p - 1 gives 1. It is interesting to consider, however, the minimum possible exponent e > 0 for a given value of a which causes a^e = 1 mod p.

This value changes with a. For example, 1^1 = 1, but -1^2 = 1. Euler's phi function also gives further information: when working in Z/mZ, any such value of e, which we will call the order or the exponent of a, has to divide phi(m).

But "has to divide" does not necessarily mean "equal to". For instance, it is known that Z/pZ is cyclic: there is at least one value mod p such that its order is exactly p -1. But what about other Z/mZ rings?

Enter Carmichael's lambda function, which you can read about in Wikipedia. The interesting results are that lambda(m) divides phi(m), and that because of its method of calculation it will happen that lambda(m) will be much less than phi(m) the smoother the integer m is.

Now let's review an interesting example. If we had m = pq, the product of two different odd primes, then phi(m) = (p-1)(q-1). However, lambda(m) = (p-1) lcm (q-1), and since p and q are odd, then we have that lambda(m) <= phi(m) / 2. What does this mean? That Z/mZ is not cyclic.

But why is this? Because the maximum order in Z/mZ is, at most, half the number of inversible elements in that group. Therefore, any element with maximum order will only be able to generate half of the whole group, and therefore the group is periodic but not cyclic.

Furthermore, phi(m) and lambda(m) differ when it comes to factors of 2. For example, phi(2^k) = 2^{k-1}. But, if k > 2, lambda(2^k) = 2^{k-2}. Again, this means that when k > 2, Z/2^kZ is not cyclic due to the same argument shown above.

To show what a difference it makes, let's review one of my favorite values of m, 240. The value of phi(240) is 64, so there are 64 inversible elements modulo 240. However, despite that, lambda(240) = 4. Therefore, no inversible element modulo 240 is capable of generating more than 4 elements of the multiplicative subgroup. This can be generalized.

Theorem: the multiplicative subgroup of Z/mZ, (Z/mZ)*, is cyclic if and only if phi(m) = lambda(m).

Proof: we already know that lambda(m) divides phi(m), so we must have phi(m) >= lambda(m). First: if (Z/mZ)* is cyclic, then there is an element g such that its powers generate (Z/mZ)*. Clearly, there must be phi(m) different powers of g, and therefore its order is phi(m). Since lambda(m) is the minimum exponent such that every element in (Z/mZ)* becomes 1 when raised to powers, it follows that lambda(m) = phi(m). Conversely, assume that (Z/mZ)* is not cyclic and that nevertheless phi(m) = lambda(m). This would mean there is at least one g with the property of being a generator, against the hypothesis of (Z/mZ)* not being cyclic.

Now in reverse. If phi(m) > lambda(m), it means no generator can generate the whole group, and therefore we clearly have that (Z/mZ)* is not cyclic. If phi(m) = lambda(m), then there is at least one g in the (Z/mZ)* the powers of which generate the whole group because its order is phi(m), the amount of elements in the subgroup. This completes the proof.