Why does $a^n \mod p$ always result in a number with Legendre symbol as 1?

Question

I noticed that the following expression

$a^n\mod p$ where p is a prime and $n >=1$ and $n <= p$

always results in a number with Legendre Symbol (with p as the prime) as 1.

I tested it out with a couple of a & p combinations. $a = 15, p = 71$

$a = 288260533169915, p = 1007621497415251$

Generated random n's & tried it out & I got only Legendre symbols as 1

What is the reason for this?

Answer 1

Let $P$ signify a quadratic residue and $N$ signify a quadratic non-residue.

Then, $NP=N$ (i.e. non-residue $\times$ residue $=$ non-residue), $NN=P$, and so $NNN=N$.

This means that if $a$ is any quadratic non-residue $\mod{p}$, so are $a_3, a_5, \cdots.$

On the other hand, if $a$ is a quadratic residue, then so are $a_2,a_3,a_4,a_5,\cdots$.