> CORRECTED THEOREM

--Richard Brent pointed out this theorem was already shown by Gauss, and

> is that the residues relatively prime to modulus M

> form a cyclic multiplicative group if and only if

> M = 2*p^k or M=p^k or M=2 or M=4,

> with k>=1 and p = odd prime.

it is in D.Shanks: Solved & Unsolved problems, theorem 42 on page 92.