Let's calculate for a bit using this criterion. It says that we can tell whether a number \(a\) has a square root modulo \(p\) simply by checking whether \(\sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{ae}{p}\right\rfloor \) is even or odd. So let's apply it to evaluating \(\left(\frac{3}{p}\right)\) for odd primes \(p\). Equivalently, we can answer this question:

If you liked some of the integer-point counting arguments earlier, you will like this.

For this case, we care about \begin{equation*}\sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{3e}{p}\right\rfloor\; .\end{equation*} Said another way, we are adding the integer parts of \(\frac{y}{p}\) for \(y\) a multiple of six less than \(3(p-1)\).

What will a fact like this look like in general? All we care about is the parity of this sum. So, we can really ignore the terms in the sum that are 0 or 2, as they won't change the parity! That means we are really only looking at \(\left\lfloor\frac{3e}{p}\right\rfloor\) for \(3e\) that are between \(p\) and \(2p\), since ones less than \(p\) are 0 and there can't be any number bigger than \(3p\) if we only let \(e\) go up to \(e=p-1\).

This means we are considering precisely even \(e\) such that \(p<3e<2p\), or all integers \(y\) such that the multiples of 6 give \begin{equation*}p<6y<2p\Rightarrow \frac{p}{6}<y<\frac{p}{3}\; .\end{equation*} We've reduced to the parity of the cardinality of this small set of integers.

It should be clear that when \(p\) moves above or below a multiple of six, this might change how many are in between. So it seems reasonable to look at primes of the form \(p=6k+ r\) when examining this. That gives \begin{equation*}\frac{p}{6}<y<\frac{p}{3}\Rightarrow \frac{6k+r}{6}<y<\frac{6k+r}{3}\Rightarrow k+\frac{r}{6}<y<2k+\frac{r}{3}\end{equation*} \begin{equation*}\Rightarrow \frac{r}{6}<y<k+\frac{r}{3}\; .\end{equation*} (This works because the cardinality of the sets will be the same if we subtract an integer.)

Try it!