I see some others have spotted the error already, but anyhow the

CORRECTED THEOREM

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.

The oversight in my proof was,

that there is only one, not two like usual, squareroots(1) mod 2,

Hence my chinese remaindering argument in the proof

does not yield extra squareroots for M=2*SomethingOdd.

Example: M=10=2*5, the powers of 3 generate: 1,3,9,7.

And golly, wikipedia already knew this theorem:

http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n
http://en.wikipedia.org/wiki/Primitive_root_modulo_n
which Eric Weisstein cites as on page 209 of

D.M.Burton: The Order of an Integer Modulo N,

Primitive Roots for Primes, and

Composite Numbers Having Primitive Roots.

sections 8.1-8.3 in Elementary Number Theory, 4th ed. Dubuque, IA: William C. Brown Publishers (1989) pages 184-209.

What is more interesting, and also mentioned in this wikipedia article,

is the fact that if M is a power of 2, then the group is "almost cyclic"

specifically if M=2^k then the multiplicative group on the odd residues mod M

has structure

(cyclic 2^(k-2)) x (2).

Example: M=32.

powers of 3:

1,3,9,27,17,19,25,11,

generates exactly half the odd residues, and 5 is

a coset representative to get the other half.

Gauss proved this by showing 3 is always a generator.