Dr Math says, "The quadratic residues are just the squares modulo n".

Consider a number n. The remainders left when the perfect squares (of numbers less than n) are divided by n are called the quadratic residues modulo n. If you're not a quadratic residue, then you're a quadratic non-residue.

Now, (-a)^2 = (a)^2. Since we're doing all our calculations modulo n, (-a) becomes (n - a). So (n - a)^2 = (a)^2. That means that if a number is a quadratic residue, then it'll be a quadratic residue twice; and if it not a quadratic residue, well, then it will never be a quadratic residue. That is what the specks mean when they say that "x^2 = a (mod n) has either 2q roots, or none".*

What this also means is that there are atmost (n - 1)/2 quadratic residues modulo n. The -1 is there for exculding 0 which makes a fuss while eating his vegetables.

Now, if n is a odd prime (i.e. it is a prime that is not 2), we can further go on to show that a quadratic residue can be a quadratic residue _exactly_ twice. Which then means that there are exactly (p - 1)/2 quadratic residues modulo p, where p is a prime. Note that we don't need to bother with the floor functions et. al., since we know for sure that (p - 1) will be even.

*I am missing one case here. What happens when n is even? Well, for the 'middlemost' a, we have (n - a) = a. For example, (10 - 5) = (5) mod 10. So both the roots will actually be the same a, and there is actually only a single root. Another victory for the vigilant colonelmustard and his troops.