Results 1 to 4 of 4

Thread: 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 $\displaystyle \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.)

    $\displaystyle \varphi (13) \ = \ 12 $

    $\displaystyle 2 $ has order $\displaystyle 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 $\displaystyle x^{11} \ = \ 4(mod \ 13) $.

    My solution.......

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

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

    Now, letting $\displaystyle x = 2^y $, then

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

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

    Multiplying both sides by 4 gives

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

    $\displaystyle 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 $\displaystyle 13=4\cdot 3 +1$. We have: $\displaystyle
    \left( {{\textstyle{2 \over {13}}}} \right) \equiv 2^6 = 64 \equiv - 1\left( {\bmod .13} \right)
    $ (so it is a non-quadratic residue by Euler's Criterion) and $\displaystyle
    2^2 \equiv 4
    \not \equiv -1
    \left( {\bmod .13} \right)
    $ so 2 is indeed a primitive root. Now $\displaystyle
    \left( {{\textstyle{3 \over {13}}}} \right) \equiv 3^6 = 729 \equiv 1\left( {\bmod .13} \right)
    $ and hence 3 is a quadratic residue and therefore not a primitive root.

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

    Note that: $\displaystyle
    11 \equiv - 1\left( {\bmod .12} \right)
    $ and therefore $\displaystyle
    -y \equiv 2\left( {\bmod .12} \right)
    $ and so $\displaystyle 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
    $\displaystyle

    y\equiv{-2\equiv{10}}(\bmod.12)
    $

    and substitute it back to find $\displaystyle 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
    $\displaystyle

    y\equiv{-2\equiv{10}}(\bmod.12)
    $

    and substitute it back to find $\displaystyle x $?
    Exactly . Remember to take $\displaystyle 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: Apr 23rd 2010, 06:57 PM
  2. primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 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: 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


/mathhelpforum @mathhelpforum