Results 1 to 5 of 5

Math Help - Proof: Primative root mod(p)

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    2

    Proof: Primative root mod(p)

    hi, i'm stuck on this assignment question. my teacher said it's really easy so i think i'm just missing something obvious? thanks


    Let p be an odd prime and g be a primitive root modulo p. Let y be an integer such
    that gcd(y, p-1) = 1. Show that g^y is a primitive root modulo p.
    Last edited by mr fantastic; August 11th 2010 at 07:58 PM. Reason: Restored deleted question.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    If gcd(y,p-1)=1 then {1,2,3,...,p-1}={y,2y,3y,...,(p-1)y} mod p.

    Given a=g^b, then a=(g^y)^(bc) where c=y^(-1) mod(p-1)
    Last edited by chiph588@; August 10th 2010 at 06:53 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by davidodea View Post
    hi, i'm stuck on this assignment question. my teacher said it's really easy so i think i'm just missing something obvious? thanks


    Let p be an odd prime and g be a primitive root modulo p. Let y be an integer such
    that gcd(y, p-1) = 1. Show that g^y is a primitive root modulo p.
    Here's what I think.... The goal is to show that the order of g^y modulo p is the equal to p-1 (namely, primitive root).
    Let the integer t be the order of g^y modulo p , so t|p-1 . Also, (g^y)^t=g^{yt}\equiv 1\bmod p and the order of g modulo p must divide yt , so p-1|yt. Now you can use gcd(y,p-1) ...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2010
    Posts
    2
    Quote Originally Posted by chiph588@ View Post
    If gcd(y,p-1)=1 then {1,2,3,...,p-1}={y,2y,3y,...,(p-1)y} mod(p-1).
    Hi, thanks for the reply..
    Sorry, i don't understand why if the gcd(y,p-1)=1 then 1=y [mod (p-1)]

    eg for p=17 and y=39
    gcd(39,16)=1 , but 1 =/ 39 mod 16?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by davidodea View Post
    Hi, thanks for the reply..
    Sorry, i don't understand why if the gcd(y,p-1)=1 then 1=y [mod (p-1)]

    eg for p=17 and y=39
    gcd(39,16)=1 , but 1 =/ 39 mod 16?
    That's not what I meant. Let  \displaystyle A=\{1,2,3,\ldots,p-1\} and  \displaystyle B=\{y,2y,3y,\ldots,(p-1)y\} .

    I'm saying that for all  a\in A, \; \exists \; b\in B such that  a\equiv b\bmod{p} and for all  b\in B, \; \exists \; a\in A such that  a\equiv b\bmod{p} .

    So I say  A\equiv B\bmod{p} .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. N-th Root Irrationality Proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 5th 2011, 10:25 PM
  2. Proof there is a root
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: April 27th 2010, 01:11 AM
  3. Primative roots and indexes
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 9th 2009, 08:25 AM
  4. Root 2 recursion proof help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 27th 2009, 03:31 AM
  5. [SOLVED] proof of root 3
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 5th 2009, 12:07 AM

/mathhelpforum @mathhelpforum