# Prove that $a^2,a^4,…,a^{p-1}$ are the quadratic residues modulo $p$.

Let $p$ be an odd prime $(p,a)=1$. Then, by Fermat's theorem, $a^{p-1}$ is congruent to $1$ (mod $p$). If $p-1$ is the smallest positive value of $e$ such that $a^e$ is congruent to $1$(mod $p$), prove that $a^2,a^4,...,a^{p-1}$ are the quadratic residues modulo $p$.

My solution:

The Legendre symbol $(a/p) = \pm1$since $(p,a)=1$.

Then $(a^2/p)=(a/p)^2=1$.

$(a^4/p)=(a^2/p)^2=1$

...

$(a^{p-1}/p)=(a^{(p-1)/2}/p)^2=1$

Am I correct? What is "$p-1$ is the smallest positive value of $e$ such that $a^e$ is congruent to $1 \pmod p$" for?

If $e=p-1$ is the smallest positive integer such that $a^e \equiv 1 \pmod p$ then $a$ is a primitive root modulo $p$. This means the set $\{a,a^2,...,a^{p-1}\}$ is the same as $\{1,...,p-1\}$ after reduction mod $p$. Then clearly all the even powers of $a^{2k}$ for $k=1,2,...,(p-1)/2$ are the quadratic residues since in particular $(a^k)^2\equiv a^{2k} \pmod p$