Finding an element of order $67$ modulo $2011$. Suppose that we are given $p= 2011$, where $3$ is a primitive root (this is a given). Here is the question:

Find an element of order $67$.

I know that $e_{p}(a) =$ (the smallest exponent $e \geq 1$ such that $a^e \equiv 1$ (mod $p$). But, this turns into the Discrete Log Problem, which makes it difficult to solve for $e$ since there is no general way of approaching these types of problems. How else can I approach this problem?
 A: $2011$ is prime and $|3|$ is given to be $2010$.  So that $3^{2010} \equiv 1 \mod 2011$ and for any $k < 2011$ $3^k \not \equiv 1 \mod 2011$.
We don't have to prove that.  We were told that.
Notice that $(3^k)^m = 3^{km}$ so if $mk = 2010$ then $(3^k)^m \equiv 3^{km} = 3^{2010} \equiv 1 \mod 2011$.
So Let $m = 3^{\frac {2010}{67}}$.  Then $m^{67} = 3^{2010} \equiv 1 \mod 2011$ and if $k < 67$ then $m^k = 3^{\frac {2010}{67}*k}$ and $\frac {2010}{67}*k < 2010$ and so $m^k = 3^{\frac {2010}{67}*k}\not \equiv 1 \mod 2011$.
So $m = 3^{\frac {2010}{67}}$ has order $67$.
That's all there is to it.
A: You are, in effect, told that $a=3^{30}\not\equiv1$ mod $2011$, so you know that $a^{67}=3^{30\cdot67}=3^{2010}\equiv1$ mod $2011$, by Fermat's little theorem for the prime $2011$.  This means the order of $a$ is a divisor of $67$. But since $67$ is prime, that divisor can only be $67$ itself.
If you want to find the residue $a=3^{30}$ mod $2011$ explicitly, you've got some squaring to do first:
$$\begin{align}
3^2&=9\\
3^4&=9^2=81\\
3^8&=81^2=6561\equiv528\\
3^{16}&=528^2=278784\equiv1266
\end{align}$$
so that
$$\begin{align}
3^{30}&=3^{16+8+4+2}\\
&\equiv1266\cdot528\cdot81\cdot9\\
&=(1266\cdot9)\cdot(528\cdot81)\\
&=11394\cdot42768\\
&\equiv1339\cdot537\\
&=719043\\
&\equiv1116
\end{align}$$
