Results 1 to 6 of 6

Math Help - Primitive Roots - product of integers <= n and rel prime to n

  1. #1
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169

    Primitive Roots - product of integers <= n and rel prime to n

    (1) Show that if n is an integer which has primitive roots, then the product of the integers less than or equal to n and relatively prime to n == -1(mod n).
    (2) Show that (1) is not true if n does not have a primitive root.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by tarheelborn View Post
    (1) Show that if n is an integer which has primitive roots, then the product of the integers less than or equal to n and relatively prime to n == -1(mod n).
    (2) Show that (1) is not true if n does not have a primitive root.


    The natural number n has a primitive root a iff \left(\mathbb{Z}\slash n\mathbb{Z}\right)^{*} = \{a,a^2,\ldots,a^{\phi(n)}=1\}\Longleftrightarrow 1\cdot a\cdot a^2\cdot\ldots\cdot a^{\phi(n)-1}=a^{\sum^{\phi(n)-1}_{i=1}i}=a^{\frac{(\phi(n)-1)\phi(n)}{2}}= \left(a^{\frac{\phi(n)}{2}}\right)^{\phi(n)-1}=-1 ...

    Explain the above, in particular the very last equality.

    Tonio

    Tonio
    Last edited by tonio; March 24th 2010 at 01:03 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169
    I know that a^phi(n)==1(mod n), but I am not sure how to explain the rest of it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169
    OK, I think this may be it. Since g^phi(n)==1(mod n) and g^(phi(n)-1)/2==-1(mod n), then their product would be -1(mod n). Done. Right?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169
    Also, I need to show that this is not true if n does not have a primitive root.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by tarheelborn View Post
    Also, I need to show that this is not true if n does not have a primitive root.

    The demonstration is an if and only if one, so both directions are already contained in it....what part you didn't get? That there's a primitive root w of n means that all the units in \mathbb{Z}\slash n\mathbb{Z} , i.e. the elements of \left(\mathbb{Z}\slash n\mathbb{Z}\right)^{*} , i.e. all the integers modulo n which are coprime to n, are a power of w <==> the group \left(\mathbb{Z}\slash n\mathbb{Z}\right)^{*} is cyclic of order \phi(n)...in the last equality I used that \phi(n) is even for any n\geq 3 ...

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. sophie germain prime primitive root
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 24th 2010, 09:17 AM
  2. Order of integers and primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 31st 2010, 05:43 PM
  3. Primitive Root of odd prime p
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 2nd 2010, 11:10 AM
  4. primitive root of a prime
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 13th 2009, 08:39 PM
  5. Primitive pth root of unity of a prime p
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 23rd 2008, 06:38 AM

Search Tags


/mathhelpforum @mathhelpforum