Section17.3Using Eisenstein's Criterion

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\; \]

Subsection17.3.1Does \(3\) have a square root?

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)\).

Example17.3.1
  • \(p=7\): We have \[\left\lfloor\frac{6}{7}\right\rfloor+\left\lfloor\frac{12}{7}\right\rfloor+\left\lfloor\frac{18}{7}\right\rfloor=0+1+2=3\]
  • \(p=11\): We have \[\left\lfloor\frac{6}{11}\right\rfloor+\left\lfloor\frac{12}{11}\right\rfloor+\left\lfloor\frac{18}{11}\right\rfloor+\left\lfloor\frac{24}{11}\right\rfloor+\left\lfloor\frac{30}{11}\right\rfloor=0+1+1+2+2=6\]

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:

  • The parity of \(k\).
  • The parity of the size of the set of integer \(y\) such that \(\frac{r}{6}<y<\frac{r}{3}\).

These can be easily dealt with.

  • The parity of \(k\).
    • If \(k\) is even, then \(k=2\ell\) and \(p=6k+r=12\ell+r\).
    • If not, then \(k=2\ell+1\) and \(p=6k+r=12\ell+6+r\).
  • There are two possible residues \(r\) modulo 6 for prime \(p\). Either \(r=1\) or \(r=5\).
    • If \(r=1\), we are looking for \(y\) such that \(\frac{1}{6}<y<\frac{1}{3}\), of which there are none.
    • If \(r=5\), we are looking for \(y\) such that \(\frac{5}{6}<y<\frac{5}{3}\), of which there is one.

Combining these, we see that

  • If \(p=12\ell+1\) we add two even numbers, so 3 is a QR.
  • If \(p=12\ell+5\), we add an even number and 1, so 3 is not a QR.
  • If \(p=12\ell+6+1=12\ell+7\), we add an odd and zero, so 3 is not a QR.
  • If \(p=12\ell+6+5=12\ell +11\), we add an odd and 1, which is even, so 3 is a QR.
We can express this more succinctly.