Results 1 to 4 of 4

Math Help - i need help in primitive roots

  1. #1
    Newbie
    Joined
    Dec 2007
    Posts
    12

    i need help in primitive roots

    i have 2 problem and need ur help

    let r be a primitive root of the integer n . prove that r^k is a primitive root of n if and only if gcd(k,phi(n))=1


    ***********

    for prime p>3 prove that the primitive root of p occur in pairs r,r' where rr' equivelent to 1(modp)

    hint (take r' as r^(p-2) )


    ******

    plz any one can help me with them ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by midosoft View Post
    i have 2 problem and need ur help

    let r be a primitive root of the integer n . prove that r^k is a primitive root of n if and only if gcd(k,phi(n))=1
    Let n>2 be a positive integer. Say that n has a primitive root, call it r. Consider the set \{ r,r^2,...,r^{\phi(n)} \}, this set is the complete set of numbers relatively prime to n. Now s=r^k is a primitive root means \{ s,s^2,...,s^{\phi(n)} \} must also be a complete set of numbers relatively prime to n. If \gcd (k, \phi(n)) = d then s^{\phi(n)/d} = \left( r^{\phi (n)} \right)^{k/d} \equiv 1 (\bmod n) thus the order of s is at least \phi(n)/d but since we require that \phi(n)/d \geq \phi(n) it means the only possible value for d is 1. Now (for the converse) say \gcd (k,\phi(n)) = 1. We will argue that \{s,s^2,...,s^{\phi(n)}\} cannot be congruent to eachother and hence by pigeonhole principle they must contain all the relatively prime numbers to n. Note, if s^i \equiv s^j (\bmod n) then r^{ki} \equiv r^{kj} (\bmod n) but that means ki \equiv kj (\bmod \phi(n)) since \gcd(k,\phi(n))=1 it means i\equiv j (\bmod \phi(n)) so i=j since 1\leq i,j\leq \phi(n). Thus, this shows that the only numbers congruent are those to themselves, i.e. distinct numbers leave distinct remainders mod n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by midosoft View Post
    for prime p>3 prove that the primitive root of p occur in pairs r,r' where rr' equivelent to 1(modp)

    hint (take r' as r^(p-2) )
    By the first excerise if r is a primitive root then r^k is a primitive root iff \gcd(k, p - 1) = 1 so there are \phi(p-1) such exponents which can be paired because \phi (p-1) is even since p>3. Let r_1,...,r_m be these primitive roots. Then the equation r_i x \equiv 1(\bmod p) has a solution since \gcd (r_i,p)=1 it means for r_1 be can pick a r_2 so that r_1r_2\equiv 1; for r_3 we can pick a r_4 so that r_3r_4\equiv 1, and so on.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2007
    Posts
    12
    i don't know what i say man

    very thnx
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 10th 2011, 05:15 PM
  2. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 17th 2008, 08:09 PM
  3. Primitive roots
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 15th 2007, 09:19 AM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 21st 2006, 07:05 AM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 18th 2006, 01:43 PM

Search Tags


/mathhelpforum @mathhelpforum