Results 1 to 4 of 4

Math Help - Orders, Primitive Roots

  1. #1
    Member Maccaman's Avatar
    Joined
    Sep 2008
    Posts
    85

    Orders, Primitive Roots

    Hi All,
    I was hoping that someone could check my answers/working for the following questions.
    Question 1)
    Find the order of 2 & 3 in  \mathbb{Z} / 13 \mathbb{Z}. Which one's the primitive root?
    (I don't know the latex to show all my working so I wont show all of it.)

     \varphi (13) \ = \ 12

     2 has order  12 \ = \ \varphi(13) and is therefore a primitive root.

    3 has order 3 and isn't a primitive root.

    Question 2) Using the primitive root, solve  x^{11} \ = \ 4(mod \ 13) .

    My solution.......

     4 \ \equiv \ 2^2 \ (mod \ 13)

    Since 2 is a primitive root,  x \ is some power of  2 \ mod \ 13

    Now, letting  x = 2^y , then

     x^{11} \ \equiv \ 4 \ (mod \ 13) becomes  (2^y)^{11}  = 2^{11y} \ \equiv \ 2^2 \ (mod \ 13)

    Then since 2 has order  \varphi (13) = 12,
     11y \equiv \ 2(mod \ 12) .

    Multiplying both sides by 4 gives

     y = 8 \ mod \ 12 which we substitute back to get

     x \ \equiv \ 2^8 \ \equiv \ 4 \ mod \ 12

    Is this correct? Any help would be greatly appreciated.
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Question1) Your Answer is correct.

    Here's a fast way of doing it:

    Read here and note that 13=4\cdot 3 +1. We have: <br />
\left( {{\textstyle{2 \over {13}}}} \right) \equiv 2^6  = 64 \equiv  - 1\left( {\bmod .13} \right)<br />
(so it is a non-quadratic residue by Euler's Criterion) and <br />
2^2  \equiv 4<br />
\not  \equiv -1<br />
\left( {\bmod .13} \right)<br />
so 2 is indeed a primitive root. Now <br />
\left( {{\textstyle{3 \over {13}}}} \right) \equiv 3^6  = 729 \equiv 1\left( {\bmod .13} \right)<br />
and hence 3 is a quadratic residue and therefore not a primitive root.

    Question2) It is all correct up to when you said: <br />
11y \equiv 2\left( {\bmod .12} \right)<br />

    Note that: <br />
11 \equiv  - 1\left( {\bmod .12} \right)<br />
and therefore <br />
-y \equiv 2\left( {\bmod .12} \right)<br />
and so y\equiv{-2\equiv{10}}(\bmod.12)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Maccaman's Avatar
    Joined
    Sep 2008
    Posts
    85
    Thanks for the help.

    Just wanted to confirm that I now take
    <br /> <br />
y\equiv{-2\equiv{10}}(\bmod.12)<br />

    and substitute it back to find  x ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by Maccaman View Post
    Thanks for the help.

    Just wanted to confirm that I now take
    <br /> <br />
y\equiv{-2\equiv{10}}(\bmod.12)<br />

    and substitute it back to find  x ?
    Exactly . Remember to take  x in module 13
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. x^7 = 12 mod 29 (primitive roots)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2010, 06:57 PM
  2. primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 11th 2009, 05:03 AM
  3. Primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 6th 2008, 09:00 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