Basically title: Why is $\left( \frac {a}{p}\right)$ (the Legendre symbol) $= 1$ equivalent to $p$ satisfying some condition mod $4a$, for odd prime $p$? (For example, $\left( \frac {3}{p}\right)=1 \iff p=1$ or $7$ mod $12$).
I was specifically wondering why the congruence is modulo $4a$. Thanks!
Lets first consider ony the case where $a$ is an odd prime. Then you can use the "law of quadratic reciprocity" and the explicit formula $\left(\frac{a}{p}\right)=a^{(p-1)/2}\pmod p$ to compute: \begin{align} \left(\frac{a}{p}\right)&= \left(\frac{p}{a}\right)(-1)^{(p-1)(a-1)/4} \\ &= p^{(a-1)/2}(-1)^{(p-1)(a-1)/4}\pmod a \\ &= \begin{cases} p^{(a-1)/2}\pmod a & \text{ if $a=1\pmod4$} \\ (-p)^{(a-1)/2}\pmod a & \text{ if $a=3\pmod4$} \\ \end{cases} \end{align} In both cases you can just list all possibilities $\pmod a$. And if you combine the two cases, you get a condition $\pmod {4a}$. (Though of course for some values of $a$, this condition can be simplified to one with a smaller modulus. As noted by @Infinity_hunter in a comment).
The case $a=2$ can be done explicity, see here for example.
The case of non-primes $a$ can be handled using multiplicativity $$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$ where you have to combine conditions $\pmod a$ and $\pmod b$ to a single condition $\pmod{ab}$. But Im gonna leave the details up to you :)