# Using Legendre Notation

By the Legendre Notation, $x^2\equiv{a}\pmod{p}$ has a solution if $a^{\frac{p-1}{2}}\equiv{1}\pmod{p}$.

Now, I've been told (by the text I'm learning) to consider $p=q+4a$, where $p,q$ are odd primes. I need to show via Legendre symbols that $$\left(\frac{a}{q}\right)=\left(\frac{p}{q}\right)$$ There is a theorem that says if $a\equiv{b}\pmod{p}$, then $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$, so i'm thinking this is the way to go. But I would have to then show that $a\equiv{p}\pmod{q}$, and I don't quite have that (i don't think) with the identity $p=q+4a$. By the mod definition I can show that $p\equiv{q}\pmod{a}$ but that is not what I need. The other angle i was thinking was that since $p=q+4a$ and $p,q$ are odd primes, then $p,q$ are congruent to either $1$ or $3$ $\pmod{4}$, and perhaps at that point using reciprocity. Any hints welcome please.

We have $p$ congruent to $4a$ modulo $q$. Thus $(p/q)=(4a/q)$. But $(4a/q)=(4/q)(a/q)=(a/q)$ since $(4/q)=1$ ($4$ is a perfect square).