Results 1 to 3 of 3

Math Help - Primitive roots

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    45

    Primitive roots

    Show that if m is a number having primitive roots, then the product of the positive integers less than or equal to m and relatively prime to m is congruent to -1 (\mod{m}).

    m has primitive roots means there is a least residue a such that a^{\phi(m)} \equiv 1 (\mod{m})

    Since a is a primitive root of m, then the least residues (\mod{m}) of a, a^2, ..., a^{\phi(m)} are a permutation of the \phi(m) positive integers less than m and relatively prime to m.

    So the congruency to look at is (a * a^2 * ... * a^{\phi(m)}) \equiv -1 (\mod{m}) correct??? I have been looking at this congruency and failing to make it true.

    Thanks for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: Primitive roots

    Quote Originally Posted by Zalren View Post
    Show that if m is a number having primitive roots, then the product of the positive integers less than or equal to m and relatively prime to m is congruent to -1 (\mod{m}).

    m has primitive roots means there is a least residue a such that a^{\phi(m)} \equiv 1 (\mod{m})

    Since a is a primitive root of m, then the least residues (\mod{m}) of a, a^2, ..., a^{\phi(m)} are a permutation of the \phi(m) positive integers less than m and relatively prime to m.

    So the congruency to look at is (a * a^2 * ... * a^{\phi(m)}) \equiv -1 (\mod{m}) correct??? I have been looking at this congruency and failing to make it true.

    Thanks for any help.
    If m has primitive roots then \phi(m) is an even number. So the group of primitive roots has even order. Two of its elements are 1 and m1 (and of course m-1\equiv-1\pmod m). The remaining elements can be paired off, each pair consisting of an element and its inverse. The product of each such pair is by definition \equiv 1\pmod m. So the product of all the elements of the group is \equiv-1\pmod m.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    45

    Re: Primitive roots

    Thanks! Now that you told me that, it was so simple. I have been wrestling with this all weekend. Thanks again!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 24th 2010, 02:15 PM
  2. primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 24th 2009, 01:27 PM
  3. Primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 6th 2008, 10:00 AM
  4. i need help in primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 13th 2007, 05:51 PM
  5. Help With primitive roots
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 28th 2007, 02:37 PM

/mathhelpforum @mathhelpforum