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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.