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?
On
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}$$
$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.