Question 17.3.1.
When does \(3\) have a square root modulo \(p\text{?}\)
Section 17.3 Using Eisenstein’s Criterion
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\text{.}\) Equivalently, we can answer this question, which we only began answering in Exercise 16.8.15.
If you liked some of the integer-point counting arguments earlier, you will like this. For the case \(a=3\text{,}\) we care about
\begin{equation*}
\sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{3e}{p}\right\rfloor\text{.}
\end{equation*}
Said another way, we are adding the integer parts of \(\frac{y}{p}\) for \(y\) a multiple of six that is less than \(3(p-1)\text{.}\)
Example 17.3.2.
Let’s try with \(p=7\text{:}\) We have
\begin{equation*}
\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
\end{equation*}
so Theorem 17.2.8 asks for \((-1)^3=-1\text{,}\) so \(\left(\frac{3}{7}\right)=-1\) and \(3\not\equiv s^2\) (mod \(7\)) for any \(s\text{.}\)
What about with \(p=11\text{?}\) Calculating the exponent gives
\begin{equation*}
\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
\end{equation*}
This is even, and we already saw several times that this correctly implies 3 is a QR.
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\text{,}\) since ones less than \(p\) go to zero and there can’t be any number bigger than \(3p\) if we only let \(e\) go up to \(e=p-1\text{.}\)
This means we are considering precisely even \(e\) such that \(p<3e<2p\text{,}\) or all integers \(y\) such that the multiples of 6 give
\begin{equation*}
p<6y<2p\Rightarrow \frac{p}{6}<y<\frac{p}{3}\text{.}
\end{equation*}
Notice we have reduced the entire computation to finding the parity of the cardinality of this small set of integers.
It should be clear that as we think of different \(p\text{,}\) the change in the set of \(y\) would come when \(p\) moves above or below a multiple of six. 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}\text{.}
\end{equation*}
(This works because the cardinality of the sets will be the same if we subtract integers from the endpoints.)
Claim 17.3.3.
Both of the parities we are adding can be easily computed:
- The parity of \(k\text{.}\)
- The parity of the size of the set of integers \(y\) such that \(\frac{r}{6}<y<\frac{r}{3}\text{.}\)
The sum of these two parities should be the parity of the set between \(\frac{r}{6}\) and \(k+\frac{r}{3}\text{.}\)
Proof.
We will actually compute both parities directly. The parity of \(k\) has two options.
- If \(k\) is even, then \(k=2\ell\) and \(p=6k+r=12\ell+r\text{.}\)
- If not, then \(k=2\ell+1\) and \(p=6k+r=12\ell+6+r\text{.}\)
To compute the second part, we first note that for prime \(p\text{,}\) the only possible residues \(r\) modulo \(6\) are \(r=1\) or \(r=5\text{.}\)
- If \(r=1\text{,}\) we are looking for \(y\) such that \(\frac{1}{6}<y<\frac{1}{3}\text{,}\) of which there are none.
- If \(r=5\text{,}\) we are looking for \(y\) such that \(\frac{5}{6}<y<\frac{5}{3}\text{,}\) of which there is one.
Proposition 17.3.4.
Three is a quadratic residue (or not) in the following circumstances.
- \(\left(\frac{3}{p}\right)=1\) if \(p\equiv \pm 1\) (mod \(12\))
- \(\left(\frac{3}{p}\right)=-1\) if \(p\equiv \pm 5\) (mod \(12\))
Proof.
Combine the facts in Claim 17.3.3. We see that
- If \(p=12\ell+1\) we add two even numbers, so 3 is a QR.
- If \(p=12\ell+5\text{,}\) we add an even number and 1, so 3 is not a QR.
- If \(p=12\ell+6+1=12\ell+7\text{,}\) we add an odd and zero, so 3 is not a QR.
- If \(p=12\ell+6+5=12\ell +11\text{,}\) we add an odd and 1, which is even, so 3 is a QR.
Try it!
Compare to Exercise 16.8.15 as well as Example 16.5.4.
