Orders, Primitive Roots

**Maccaman** · March 29th 2009, 01:56 AM

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

**PaulRS** · March 29th 2009, 05:01 AM

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