Loading ...
Sorry, an error occurred while loading the content.

24797cyclicity theorem correction

Expand Messages
  • WarrenS
    Jan 7, 2013
    • 0 Attachment
      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.
    • Show all 2 messages in this topic