Primitive root modulo $p=8t + 3$ 
Suppose that p is a prime of the form $8t +3$ and that $q=(p-1)/2$ is also a prime. Show that 2 is a primitive root modulo p. 

We must show that $ 2^{(p-1)} \equiv1 \ (mod \ p) $ for this we use the fact that $x^{(p-1)} -1\equiv (x-1)(x-2) \dots(x-(p-1)) \ (mod \ p) $ as the right side is zero then $x^{(p-1)} \equiv 1 \ (mod \ p)$ then $ 2^{(p-1)} \equiv1 \ (mod \ p) $.
Now we see that what $ 2^{(n)} \not\equiv1 \ (mod \ p) $ for $n < p-1$, how could I check this? 
 A: You know that the prime factorization of $p-1$ is $p-1 = 2 \cdot q$. So the possible orders of the element $2 \in (\mathbb{Z}/p\mathbb{Z})^*$ are the divisors of $p-1$, and these are $1,2,q$ and $p-1$. Try to look at all these possibilities and find that in each possible case $2$ is a primitive root. The case of order $2$ does actually occur (for $p = 3$), but in that case $2 = p - 1$, so things are good anyway.
A: You want to calculate the multiplicative order of $2$ modulo $p$.  Note that $p-1 = 2q$, so the only possible orders are $q$, and $2q$ (technically $1$ and $2$ are possibilities, but they are easily eliminated).
So this problem is really about showing that $2^q \not\equiv 1 (\rm{mod}\ p)$, rather than $2^p \equiv 1 (\rm{mod}\ p)$.
$2^{\frac{p-1}{2}} (\rm{mod}\ p)$ is just the Legendre symbol $\left(\frac{2}{p}\right)$, which is a standard quantity that comes up as a supplement to the law of quadratic reciprocity.
A: Hint: If $2^n = 1\mod p$, then $n \in \{2,q,p-1\}$. If it is $2$, then $3 = 2^2 - 1 = pk$ for some $k$, which is a contradiction. If it is $q$, what can you say? 
A: Hint: Euler's Criterion and Wilson's Theorem may be enlightening to anyone trying to show that $2^q \not\equiv 1 (\rm{mod}\ p)$. 
An informative proof of Euler's Criterion
