NTIC Using Eisenstein's Criterion

🔗

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.

🔗

Question 17.3.1.

When does $3$ have a square root modulo $p\text{?}$

🔗

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!

xxxxxxxxxx
 
@interact
def _(p=prime_range(5,50)):
    L = solve_mod(x^2==3,p)
    pretty_print(html(r"$%s\equiv %s\text{ (mod }12)$ and $\left(\frac{3}{%s}\right)=%s$"%(p,p%12,p, legendre_symbol(3,p))))
    if L:
        pretty_print(html(r"And it turns out $%s^2\equiv %s$, $%s^2\equiv %s$ (mod $%s$)"%(L[0][0],L[0][0]^2,L[1][0],L[0][0]^2,p)))

🔗

Compare to Exercise 16.8.15.