# Orders, Primitive Roots

• Mar 29th 2009, 01:56 AM
Maccaman
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 :)
• Mar 29th 2009, 05:01 AM
PaulRS

Here's a fast way of doing it:

Read here and note that $13=4\cdot 3 +1$. We have: $
\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 $
2^2 \equiv 4
\not \equiv -1
\left( {\bmod .13} \right)
$
so 2 is indeed a primitive root. Now $
\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: $
11y \equiv 2\left( {\bmod .12} \right)
$

Note that: $
11 \equiv - 1\left( {\bmod .12} \right)
$
and therefore $
-y \equiv 2\left( {\bmod .12} \right)
$
and so $y\equiv{-2\equiv{10}}(\bmod.12)$
• Mar 29th 2009, 05:18 AM
Maccaman
Thanks for the help.

Just wanted to confirm that I now take
$

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

and substitute it back to find $x$?
• Mar 29th 2009, 05:20 AM
PaulRS
Quote:

Originally Posted by Maccaman
Thanks for the help.

Just wanted to confirm that I now take
$

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

and substitute it back to find $x$?

Exactly :) . Remember to take $x$ in module 13