Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - How to find a primitive root of N

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    11

    How to find a primitive root of N

    Let N have primitive roots .Which the way does find all primitive roots generally ? I think if testing all i ,(i,N)=1, is so long
    THanks
    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 fanfan1609 View Post
    Let N have primitive roots .Which the way does find all primitive roots generally ? I think if testing all i ,(i,N)=1, is so long
    THanks
    There is no known way to find primitive roots. There are methods which make it faster. Of course, a computer program is the best way to go. See this.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2008
    Posts
    11
    Quote Originally Posted by ThePerfectHacker View Post
    There is no known way to find primitive roots. There are methods which make it faster. Of course, a computer program is the best way to go. See this.
    I also know that way .YOu can help me my problem .
    find the primitive root of 11^2 if we know 2,3 is primitive root of 11.
    My teacher said that "if p is primitive root of N ,or p or p+N is primitive root of N^2 " but he didn't said the general primitive root of 11^2.
    You can help me ?
    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    For 11 you can use a simple fact that if p is a odd prime and (p-1)/2 is also a prime then 2 is a primitive root for p. I leave that for you to prove.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2008
    Posts
    11
    Quote Originally Posted by ThePerfectHacker View Post
    For 11 you can use a simple fact that if p is a odd prime and (p-1)/2 is also a prime then 2 is a primitive root for p. I leave that for you to prove.
    maybe i am not smart enough to know your advice.YOu can tell clearly .
    I know if p is primitive root modulo n ,p^phi(n) =1 mod(n) ,
    so how do test all i ,i<11 and (i,11)=1?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by fanfan1609 View Post
    maybe i am not smart enough to know your advice.YOu can tell clearly .
    I know if p is primitive root modulo n ,p^phi(n) =1 mod(n) ,
    so how do test all i ,i<11 and (i,11)=1?
    The direct way with to deal with 11 is to list all n with \gcd (n,11)=1 so n=1,2,...,10. And now eliminate each of these numbers. For example, take n=4. Check whether the order of 4 mod 11 is \phi(11) = 10. Remember order means the smallest exponent k so that 4^k\equiv 1(\bmod 11). But since 4^{10}\equiv 1(\bmod p) (Fermat's theorem) it follows by properties of orders that k|10 so k=1,2,5,10. Since it cannot be 1 it means you just need to check k=2,5,10. A simple calculation will show that k=5 is the order, so 4 is not a primitive root. So that eliminates one number on the list \{ 1,2,...,10\}. Now pick another number, say 2, using the approach as above you will find that k=10. So that means 2 is a primitive root mod 11. Now you can save yourself a lot of time, since you found one primitive root all other primitive roots are 2^{m} where 1\leq 1\leq 10 and \gcd(m,\phi(11)) = \gcd(m,10)=1. In this case m=1,3,7,9. Thus, 2, 2^3 \equiv 8, 2^7\equiv 7, 2^9\equiv 6 are the primitive roots.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2008
    Posts
    11
    Quote Originally Posted by ThePerfectHacker View Post
    The direct way with to deal with 11 is to list all n with \gcd (n,11)=1 so n=1,2,...,10. And now eliminate each of these numbers. For example, take n=4. Check whether the order of 4 mod 11 is \phi(11) = 10. Remember order means the smallest exponent k so that 4^k\equiv 1(\bmod 11). But since 4^{10}\equiv 1(\bmod p) (Fermat's theorem) it follows by properties of orders that k|10 so k=1,2,5,10. Since it cannot be 1 it means you just need to check k=2,5,10. A simple calculation will show that k=5 is the order, so 4 is not a primitive root. So that eliminates one number on the list \{ 1,2,...,10\}. Now pick another number, say 2, using the approach as above you will find that k=10. So that means 2 is a primitive root mod 11. Now you can save yourself a lot of time, since you found one primitive root all other primitive roots are 2^{m} where 1\leq 1\leq 10 and \gcd(m,\phi(11)) = \gcd(m,10)=1. In this case m=1,3,7,9. Thus, 2, 2^3 \equiv 8, 2^7\equiv 7, 2^9\equiv 6 are the primitive roots.
    oh .i see.Thanks very much?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by fanfan1609 View Post
    oh .i see.Thanks very much?
    In my other posts. I say that if (p-1)/2 is also a prime then 2 is a primitive root of p. Say p=11 then (11-1)/2=5 is prime, which means 2 is primitive root of 11. Now since you one primitive root you found them all.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    May 2008
    Posts
    11
    Quote Originally Posted by ThePerfectHacker View Post
    In my other posts. I say that if (p-1)/2 is also a prime then 2 is a primitive root of p. Say p=11 then (11-1)/2=5 is prime, which means 2 is primitive root of 11. Now since you one primitive root you found them all.
    if i don't misunderstand ,the way you say is if i replace 2 by another number i and (p-1)/i is prime ,then i is primitive root of n .
    Do i have mistake ?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by fanfan1609 View Post
    if i don't misunderstand ,the way you say is if i replace 2 by another number i and (p-1)/i is prime ,then i is primitive root of n .
    Do i have mistake ?
    If (p-1)/i is prime DOES NOT mean i is primitive roots of p. That only works for the case (p-1)/2. I never said this in generality.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Jun 2008
    Posts
    39
    Can you make a general statment or "rule" to determining if g^k is a primitive root? Is there a generalization?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    May 2008
    Posts
    11
    Quote Originally Posted by duggaboy View Post
    Can you make a general statment or "rule" to determining if g^k is a primitive root? Is there a generalization?
    Sorry,I don't know your question.
    If you want to determine a is a primitive root modulo n ,i think you should do something :
    1/you find phi(n)
    2/determine d with d|n
    3/you test a^d mod n if the result isn't 1 with every d ,a is a primitive root modulo n
    if you want find other primitive root ,you find e with e|phi(phi(n)) ,
    with each e ,a^e mod n is a primitive root modulo n
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Jun 2008
    Posts
    39
    but how would you find d? just choose vales and try?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    May 2008
    Posts
    11
    Quote Originally Posted by duggaboy View Post
    but how would you find d? just choose vales and try?
    it is easy to find d.For example,if n is 10 ,then d is 1,2,and 5.If with every d ,which is diffirent n, a^d mod n is not 1 ,then a is a primitive root modulo n
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by duggaboy View Post
    Can you make a general statment or "rule" to determining if g^k is a primitive root? Is there a generalization?
    If g is primitive root mod n then g^k is primitive root iff \gcd(k,\phi(n)) = 1.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: February 27th 2011, 06:59 PM
  2. Replies: 8
    Last Post: January 27th 2011, 07:57 AM
  3. Primitive root help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2008, 07:26 PM
  4. primitive root
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 28th 2008, 09:36 AM
  5. find the primitive root
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: July 30th 2006, 05:56 PM

Search Tags


/mathhelpforum @mathhelpforum