Let p be an odd prime and let g be a primitive root modulo p.
- Prove that $g^k$ is a quadratic residue modulo p if and only if k is even.
- 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})$
- Use (a) to give a quick proof of Euler's Criterion $a^{\frac{p-1}{2}} \equiv (\frac{a}{p}) (\mod p)$
Best Answer
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.