Results 1 to 8 of 8

Math Help - Find primitive roots.

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    31

    Find primitive roots.

    Hey all im stuck on this question, been attempting it for ages and i have no clue how to tackle it because the mod is so high.

    "You are given 6 is a primitive root in F_251. Find Another"

    My attempt was firstly to find how many primitive roots thier are in 251.
    I found this to be 100.

    But testing all the numbers would be far too long for a 5 mark question [Past exam paper], so i was wondering how i would tackle this problem.

    Cheers people
    David.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    If 6 is a primitive root in F_251 then 6^{-1}\equiv 6^{249} is also a primitive root. With some modulo-calculations it shouldn't be too hard to find 6^{249} (\text{mod}) 251
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    31
    Quote Originally Posted by Dinkydoe View Post
    If 6 is a primitive root in F_251 then 6^{-1}\equiv 6^{249} is also a primitive root. With some modulo-calculations it shouldn't be too hard to find 6^{249} (\text{mod}) 251
    What did you use there, like theorem wise?
    Thanks for your help, im still struggling to understand this.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    since p=251 we have that \mathbb{F}_p^* is a cyclic group of order p-1

    Hence a primitive root in this group has order p-1.

    And it's easy to show that a group element has the same order as his inverse. Thus if a is a primitive root, a^{-1} must also be a primitive root.

    and a^{-1}= a^{-1}a^{p-1}= a^{p-2}

    In this case 6^{249}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by simpleas123 View Post
    What did you use there, like theorem wise?
    Thanks for your help, im still struggling to understand this.
    From Wikipedia article, "Gauss proved that for any prime number p (with the sole exception of 3) the product of its primitive roots is ≡ 1 (mod p)."

    251 is prime.

    As for finding 6^{249}\ (\text{mod}\ 251), it can be done on paper using the binary representation of 249. The method is mentioned here, but it's kind of hard to follow, I remember a site that has lots of examples but am having a hard time with Google search at the moment.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2009
    Posts
    31
    Quote Originally Posted by undefined View Post
    From Wikipedia article, "Gauss proved that for any prime number p (with the sole exception of 3) the product of its primitive roots is ≡ 1 (mod p)."

    251 is prime.

    As for finding 6^{249}\ (\text{mod}\ 251), it can be done on paper using the binary representation of 249. The method is mentioned here, but it's kind of hard to follow, I remember a site that has lots of examples but am having a hard time with Google search at the moment.
    Thanks for your help guys, ill re-attempt it as soon as ive finished dinner
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by simpleas123 View Post
    Thanks for your help guys, ill re-attempt it as soon as ive finished dinner
    I think I bookmarked that site I mentioned and it's now a dead link... since I can't find a comparable site, I'll just write an explanation.

    First to get the binary representation of 249. On paper you can proceed as follows:

    249 \equiv 1\ (\text{mod}\ 2)

    Current binary string: 1

    \bigg\lfloor\frac{249}{2}\bigg\rfloor = 124

    124 \equiv 0\ (\text{mod}\ 2)

    Current binary string: 01

    \bigg\lfloor\frac{124}{2}\bigg\rfloor = 62

    62 \equiv 0\ (\text{mod}\ 2)

    Current binary string: 001

    \bigg\lfloor\frac{62}{2}\bigg\rfloor = 31

    31 \equiv 1\ (\text{mod}\ 2)

    Current binary string: 1001

    \bigg\lfloor\frac{31}{2}\bigg\rfloor = 15

    15 \equiv 1\ (\text{mod}\ 2)

    Current binary string: 11001

    \bigg\lfloor\frac{15}{2}\bigg\rfloor = 7

    7 \equiv 1\ (\text{mod}\ 2)

    Current binary string: 111001

    \bigg\lfloor\frac{7}{2}\bigg\rfloor = 3

    3 \equiv 1\ (\text{mod}\ 2)

    Current binary string: 1111001

    \bigg\lfloor\frac{3}{2}\bigg\rfloor = 1

    1 \equiv 1\ (\text{mod}\ 2)

    Current binary string: 11111001

    You can verify that this is the correct binary representation.

    The reason we want this is because we can now write

    6^{249} = 6^{(1+8+16+32+64+128)} = 6^1\cdot 6^8\cdot 6^{16}\cdot 6^{32}\cdot 6^{64}\cdot 6^{128}

    Here's where it all comes together.

    6^1 \equiv 6\ (\text{mod}\ 251)

    6^2 \equiv 6\cdot6 \equiv 36\ (\text{mod}\ 251)

    6^4 \equiv 36\cdot36 \equiv 1296 \equiv 41\ (\text{mod}\ 251)

    6^8 \equiv 41\cdot41 \equiv 1681 \equiv 175\ (\text{mod}\ 251)

    You can see where this is going. There aren't so many steps left, and then you'll have your final answer.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    It might also interest you to know that modular inverses can be found via the extended Euclidean algorithm. See here. It's basically the same way you solve linear Diophantines, if you've ever done that.

    Edit: I meant linear Diophantines in two variables, just for clarity.
    Last edited by undefined; May 6th 2010 at 09:04 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 5th 2011, 10:24 PM
  2. primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 24th 2009, 12:27 PM
  3. find primitive roots for mod
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 17th 2009, 03:55 PM
  4. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 15th 2008, 06:58 PM
  5. Primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 6th 2008, 09:00 AM

Search Tags


/mathhelpforum @mathhelpforum