Let $a \equiv 1 \pmod 4$ and p an odd prime. Show that the Legendre symbol $\left(\frac{a}{p}\right)$ only depends on $p \pmod a$

Question

Let $a \equiv 1 \pmod 4$ and let $p$ be an odd prime. Show that $\left( \frac{a}{p}\right)$ only depends on $p \pmod a$.

I know that $\left(\frac{a}{p}\right)=\left(\frac{p}{a}\right)$ because of the law of quadratic reciprocity. But I don't know how to go on.

Can I use Euler's criterion to prove this?