1. 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

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)$

3. 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$?

4. Originally Posted by Maccaman
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