Proving that for a quadratic residue $n \pmod p$, there exists an $a$ such that $a^2-n$ is a quadratic nonresidue $\pmod p$. I was reviewing Cipolla's Algorithm for finding the 'square root' of $n$ modulo a prime $p$.  The first step is always to find an $a$ such that $a^2-n$ is a quadratic nonresidue $\bmod p$.  It seems to just be stated without proof that there exists such an $a$, and the probability of randomly choosing a valid $a$ is approximately $\frac{1}{2}$.
I cannot seem to find any proof of this though.  It appears to be assuming that $a^2-n$ is essentially a 'random' number $\bmod p$, in which case it would be true, but certainly we have a stronger way of proving this right?
 A: Suppose not. Then the map $f:x \mapsto x-n$ sends the squares to the squares and therefore the nonsquares to the nonsquares. This property stays true if we reiterate the map. 
Take any point $a$ and consider reiterating $f$ on $a$, i.e., $f^k(a)$. This goes through all the points of $\mathbb{F}_p$ (Show that for every $b\in\mathbb{F}_p$, $f^{\frac{b-a}{n}}(a) = b$). Therefore all elements of $\mathbb{F}_p$ have the same quadratic residuosity as $a$ which is absurd.
This does not prove the harder statement saying that the probability that $a^2-n$ is a non-residue over random $a$'s is 1/2. For that you can find the original proof here, or an english version here.
A: Let $Q$ denote the set of all squares (which includes $0$ and quadratic residues), and $N$ the set of all nonsquares (quadratic nonresidues) in the $p$-element field $\mathbb F_p$. We want to show that there exists an element $q\in Q$ such that $q-n\in N$. Assuming the opposite, we will have $q-n\in Q$ whenever $q\in Q$. But then, subsequently, $0\in Q$, $-n\in Q$, $-2n\in Q$ etc, which is an obvious nonsense as the sequence $(0,-n,-2n,\dotsc)$ lists all elements of the field.
The stronger density assertion is easy to prove using Legendre's symbol: up to a very small "zero correction" (which is at most $1$ in the absolute value), the number of $a\in\mathbb F_p$ such that $a^2-n$ is a nonresidue is
  $$ \frac12\,\sum_{a=0}^{p-1} \left(1-\left( \frac{a^2-n}p \right) \right)
         = \frac12p - \frac12\sigma, $$
where
\begin{align*}
  \sigma &= \sum_{a=0}^{p-1} \left( \frac{a^2-n}p \right) \\
    &=  \sum_{b=0}^{p-1} \left( \left(\frac bp\right) + 1 \right)  
                \left( \frac{b-n}p \right) \\
    &=   \sum_{b=1}^{p-1} \left(\frac bp\right)   
                \left( \frac{b-n}p \right) \\
    &=   \sum_{b=1}^{p-1} \left(\frac{b^{-1}}p\right)   
                \left( \frac{b-n}p \right) \\
    &=   \sum_{b=1}^{p-1} \left( \frac{1-(n/b)}p \right) \\
    &=   -1.
\end{align*}
