cyclicity theorem correction
- I see some others have spotted the error already, but anyhow the
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:
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
(cyclic 2^(k-2)) x (2).
powers of 3:
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.
> 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.