Modular Mathematics, The Group of Units mod m

The Group of Units mod m

We know that the units mod p are cyclic. In other words, they can all be generated by succesive powers of a primitive root. How about the units mod p^r? We know there are φ(p^r) of them, which is p^r-1×(p-1), but how do they behave under multiplication?

Let's start with p = 2. There is only one unit mod 2, and 3 is a primitive root mod 4, so assume r is at least 3, hence n is at least 8.

Let x equal 1 mod 2^k, for some k ≥ 2. Square x, and ratchet up the exponent, from k to k+1 to k+2 etc. Start with x = 1 mod 4 (but not 1 mod 8). Square this r-3 times and find a number that is 1 mod 2^r-1, but not 1 mod 2^r. This is a nontrivial square root of 1, something other than ±1. We must square again to get 1. We may as well set x = 5, though any value 5 mod 8 will do. Thus 5 is a generator. Raising to an odd power produces something else that is 5 mod 8, and we still have to square r-2 times to reach 1, so 2^r-2 is in fact the lowest exponent that takes 5 to 1. All the lower powers of 5 are distinct.

This cycle covers half the units, namely the units that are 1 mod 4. We need another generator for the units that are 3 mod 4. Let g = 2^r-1-1. This is another nontrivial square root of 1. Multiplying by g permutes units, so g times the powers of 5 covers the remaining units, everything 3 mod 4. Since g×5^j times g×5^k = 5^j+k, the two generators, g and 5, are independent. One is a 2 cycle and the other starts a cycle of length 2^r-2.

The reasoning is similar for p^r (p odd). Again, raising to the p power ratchets the exponent. Let v be a primitive root mod p, and let g = v+p. If g^k = 1, k has to be a multiple of p-1, since v is primitive. Let h = g^p-1.

If we are unlucky, and h is 1 mod p², add p to g, giving v+2p. Use the binomial theorem to expand (g+p)^p-1. This brings in p×(p-1), and higher powers of p, and the new value of h, (v+2p)^p-1, is now 1 mod p.

For an arbitrary exponent k, evaluate h^k, starting with the factors of p in k. Each time we raise to the p, h is 1 mod the next power of p, as described earlier. If k is anything less than p^r-1, we don't reach 1. Raising to any other power, not divisible by p, leaves the lowest exponent of p unchanged. Therefore the powers of g don't reach 1 until the exponent is (p-1)×p^r-1, and g generates all the units. Once again the multiplicative group of units is cyclic.

If n is composite, use the chinese remainder theorem to evaluate the group of units. We can treat each prime power independently, then combine the cycles to describe multiplication mod n. The units mod 49*16*71 are described by four cycles running in parallel, with cycle lengths of 42, 4, 2, and 70.