Let's calculate for a bit using the criterion of Eisenstein's. Recall that it says that we can tell whether a number \(a\) has a square root modulo \(p\) simply by checking whether a certain number is even or odd. The number was \[\sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{ae}{p}\right\rfloor\; \]
Soon, we will use this to prove the great theorem I've been leading up to. Here, I will give an argument evaluating \(\left(\frac{3}{p}\right)\) for odd primes \(p\) using this criterion, but somewhat in the style of our integer-point counting.
In this case, we care about \[\sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{3e}{p}\right\rfloor\; .\] That is, we are adding the integer parts of \(\frac{y}{p}\) for \(y\) a multiple of six less than \(3(p-1)\).
But remember, all we care about is the parity of this sum. So, we can really ignore the terms that are 0 or 2! That means we are really only looking at \(\left\lfloor\frac{3e}{p}\right\rfloor\) 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 go up to \(e=p-1\).
So we are looking at all even \(e\) such that \(p<3e<2p\), or all integer \(y\) such that the multiples of 6 give \[p<6y<2p\Rightarrow \frac{p}{6}<y<\frac{p}{3}\; .\] So we really just care about the parity of the cardinality of this 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 \[\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}\Rightarrow \frac{r}{6}<y<k+\frac{r}{3}\; .\] (This works because the cardinality of the sets will be the same if we subtract an integer. )
So we are adding two numbers to get the parity we really are after:
These can be easily dealt with.
Combining these, we see that