# a) and b) Suppose a = primitive root mod p for an odd prime p. Show that $\left(\frac{a}{p}\right)$ = -1

I understand how to evaluate Legendre symbols when given discrete numbers. For example the Legendre symbol for the following: $$\left(\frac{3}{105953}\right)=\left(\frac{105953}{3}\right)=\left(\frac{2}{3}\right)=-1$$ I obtained -1 using quadratic reciprocity and fact that $$105953\equiv 1\bmod 4$$

However, I am having trouble with the following questions:

a) For which odd primes p is $$\left(\frac{-2}{p}\right) = 1$$ ?

b) Suppose a = primitive root mod p for an odd prime p. Show that $$\left(\frac{a}{p}\right)$$ = -1

By definition, Legendre symbol $$(\frac{a}{p})=1$$ if $$a$$ is quadratic residue, -1 otherwise. Primitive root $$a$$ cannot be quadratic residue because otherwise, you cannot generate the whole mod p with the primitive root $$a$$. Thus, part (b) of your question follows from this idea.

For part (a),

$$(\frac{-2}{p})=(\frac{p-2}{p})$$ since $$-2 \equiv p-2$$ (mod p)

Therefore, you have to find primes p so that there exists $$0 such that

$$x^2 \equiv p-2$$ (mod p)

Alternatively, one can use Euler's Criterion:

$$a^{(p-1)/2} \equiv (\frac{a}{p})$$ (mod p)

Solution: Of course, maybe one can directly solve the equation above. Yet, I would do in the following way:
$$(\frac{-2}{p})=(\frac{2}{p})(\frac{-1}{p})= (\frac{2}{p})(−1)^{(p−1)/2}...(1)$$

where the first equality comes from the multiplicative property of this operation. The second one is a consequence of Euler's Criterion (you can prove it):

$$(\frac{-1}{p})=(−1)^{(p−1)/2}$$

Back to the equation:

Case-1: If $$p \equiv 3$$ (mod 4) and 2 is a primitive root (mod p), then $$(1)=1$$.

Case-2: If $$p \equiv 1$$ (mod 4) and 2 is a primitive root (mod p), then $$(1)=-1$$.

In other cases, you can use the following proposition:

The prime 2 is a quadratic residue modulo an odd prime p if and only if $$p \equiv ±1$$ (mod 8). In other words: we have $$(\frac{2}{p})=(−1)^{(p^2−1)/8}$$.

You probably have recently proved rules for evaluating $$\left(\frac{-1}{p}\right)$$ and $$\left(\frac{2}{p}\right)$$. You can use these formulae to answer part a.

$$\left(\frac{-2}{p}\right) =\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right).$$

For part b, suppose $$a$$ is a primitive root and so has order $$p-1$$. Also suppose it is a quadratic residue, so that some $$s^2 \equiv a \pmod{p}$$. What does the order of $$s$$ have to be and is this possible?