Results 1 to 4 of 4

Thread: 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
    10
    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 $\displaystyle \{ r,r^2,...,r^{\phi(n)} \}$, this set is the complete set of numbers relatively prime to $\displaystyle n$. Now $\displaystyle s=r^k$ is a primitive root means $\displaystyle \{ s,s^2,...,s^{\phi(n)} \}$ must also be a complete set of numbers relatively prime to $\displaystyle n$. If $\displaystyle \gcd (k, \phi(n)) = d$ then $\displaystyle s^{\phi(n)/d} = \left( r^{\phi (n)} \right)^{k/d} \equiv 1 (\bmod n)$ thus the order of $\displaystyle s$ is at least $\displaystyle \phi(n)/d$ but since we require that $\displaystyle \phi(n)/d \geq \phi(n)$ it means the only possible value for $\displaystyle d$ is $\displaystyle 1$. Now (for the converse) say $\displaystyle \gcd (k,\phi(n)) = 1$. We will argue that $\displaystyle \{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 $\displaystyle n$. Note, if $\displaystyle s^i \equiv s^j (\bmod n)$ then $\displaystyle r^{ki} \equiv r^{kj} (\bmod n)$ but that means $\displaystyle ki \equiv kj (\bmod \phi(n))$ since $\displaystyle \gcd(k,\phi(n))=1$ it means $\displaystyle i\equiv j (\bmod \phi(n))$ so $\displaystyle i=j$ since $\displaystyle 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
    10
    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 $\displaystyle r$ is a primitive root then $\displaystyle r^k$ is a primitive root iff $\displaystyle \gcd(k, p - 1) = 1$ so there are $\displaystyle \phi(p-1)$ such exponents which can be paired because $\displaystyle \phi (p-1)$ is even since $\displaystyle p>3$. Let $\displaystyle r_1,...,r_m$ be these primitive roots. Then the equation $\displaystyle r_i x \equiv 1(\bmod p)$ has a solution since $\displaystyle \gcd (r_i,p)=1$ it means for $\displaystyle r_1$ be can pick a $\displaystyle r_2$ so that $\displaystyle r_1r_2\equiv 1$; for $\displaystyle r_3$ we can pick a $\displaystyle r_4$ so that $\displaystyle 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: Jul 10th 2011, 05:15 PM
  2. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Nov 17th 2008, 08:09 PM
  3. Primitive roots
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Mar 15th 2007, 09:19 AM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 21st 2006, 07:05 AM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 18th 2006, 01:43 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum