# Let p be an odd prime and let g be a primitive root modulo p.

Let p be an odd prime and let g be a primitive root modulo p.

1. Prove that $g^k$ is a quadratic residue modulo p if and only if k is even.
2. Use (a) to give a quick proof that the product of two nonresidues is a residue, and more generally that $(\frac{a}{p})(\frac{b}{p})=(\frac{ab}{p})$
3. Use (a) to give a quick proof of Euler's Criterion $a^{\frac{p-1}{2}} \equiv (\frac{a}{p}) (\mod p)$

For $(1)$, note that $g$ generates the multiplicative group $\mathbb{Z}_p^\times = \mathbb{Z}_p$ \ $\{0\}$. A quadratic residue $a \pmod{p}$ exists if there is an $x$ such that $x^2 = a \pmod{p}$.

Well, rewrite $x$ in terms of the generator $g$ and square it. For the other direction, simply use properties of exponentiation to rewrite $g^k$ as $(g^n)^2$ for some $n$. This will be a quadratic residue by definition.

For $(2)$, simply rewrite your two non-residues in terms of the generator and multiply them together. Is $k$ then even? If so, it is a quadratic residue.

For $(3)$, I'm not used to the Legendre symbol, so I will rewrite what you are trying to prove as:

If $a$ is a quadratic residue, then $a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$. Otherwise, $a^{\frac{p-1}{2}} \equiv -1 \pmod{p}$.

This isn't so bad. If $a$ is a quadratic residue, then $a = g^k$ for some even $k$. Hence, $a^{\frac{p-1}{2}} = (g^n)^{p-1} = (g^{p-1})^n = 1^n = 1.$ Use similar methods if $a$ is not a quadratic residue.

# For (1):

One direction is easy: if $k$ is even say $k=2m$, then $g^k=(g^m)^2$, hence $x=g^m$ is a solution to the equation $x^2 \equiv g^k \pmod{p}$.

For the other direction: assume that $g^k$ is a quadratic residue, this means $x^2 \equiv g^k \pmod{p}$ has a solution $x_0 \in \mathbb{Z}_p$. But $g$ being a primitive root implies that $\exists s \in \mathbb{N}$ such that $x_0=g^s$. Thus $$g^{2s} \equiv g^k \pmod{p}.$$ Since the order of $g$ is $p-1$, therefore $p-1$ divides $2s-k$. Now $p-1$ is even and so is $2s$, thus $k$ must be even.

Try other parts and see if you can proceed.