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

cyclicity theorem correction

Expand Messages
  • WarrenS
    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
    Message 1 of 2 , 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.
    • WarrenS
      ... --Richard Brent pointed out this theorem was already shown by Gauss, and it is in D.Shanks: Solved & Unsolved problems, theorem 42 on page 92.
      Message 2 of 2 , Jan 7, 2013
      • 0 Attachment
        > 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.

        --Richard Brent pointed out this theorem was already shown by Gauss, and
        it is in D.Shanks: Solved & Unsolved problems, theorem 42 on page 92.
      Your message has been successfully submitted and would be delivered to recipients shortly.