Results 1 to 3 of 3

Thread: Primitive roots

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    45

    Primitive roots

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

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

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

    So the congruency to look at is $\displaystyle (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
    10

    Re: Primitive roots

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

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

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

    So the congruency to look at is $\displaystyle (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 $\displaystyle \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 $\displaystyle 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 $\displaystyle \equiv 1\pmod m.$ So the product of all the elements of the group is $\displaystyle \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: Mar 24th 2010, 01:15 PM
  2. primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Feb 24th 2009, 12:27 PM
  3. Primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 6th 2008, 09:00 AM
  4. i need help in primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 13th 2007, 04:51 PM
  5. Help With primitive roots
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Oct 28th 2007, 01:37 PM

/mathhelpforum @mathhelpforum