MAT 338 Day 29 2011

2937 days ago by kcrisman

We can also calculate these things using this 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\;$$

Next time 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 of this semester.

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)$.   Let's do few examples.

• $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.

To summarize:

• $\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)

Cool!

for p in prime_range(5,50): html("$%s\equiv %s\\text{ mod }(12)$ and $\left(\\frac{3}{%s}\\right)=%s$"%(p,p%12,p,legendre_symbol(3,p)))
 5\equiv 5\text{ mod }(12) and \left(\frac{3}{5}\right)=-1 7\equiv 7\text{ mod }(12) and \left(\frac{3}{7}\right)=-1 11\equiv 11\text{ mod }(12) and \left(\frac{3}{11}\right)=1 13\equiv 1\text{ mod }(12) and \left(\frac{3}{13}\right)=1 17\equiv 5\text{ mod }(12) and \left(\frac{3}{17}\right)=-1 19\equiv 7\text{ mod }(12) and \left(\frac{3}{19}\right)=-1 23\equiv 11\text{ mod }(12) and \left(\frac{3}{23}\right)=1 29\equiv 5\text{ mod }(12) and \left(\frac{3}{29}\right)=-1 31\equiv 7\text{ mod }(12) and \left(\frac{3}{31}\right)=-1 37\equiv 1\text{ mod }(12) and \left(\frac{3}{37}\right)=1 41\equiv 5\text{ mod }(12) and \left(\frac{3}{41}\right)=-1 43\equiv 7\text{ mod }(12) and \left(\frac{3}{43}\right)=-1 47\equiv 11\text{ mod }(12) and \left(\frac{3}{47}\right)=1 5\equiv 5\text{ mod }(12) and \left(\frac{3}{5}\right)=-1 7\equiv 7\text{ mod }(12) and \left(\frac{3}{7}\right)=-1 11\equiv 11\text{ mod }(12) and \left(\frac{3}{11}\right)=1 13\equiv 1\text{ mod }(12) and \left(\frac{3}{13}\right)=1 17\equiv 5\text{ mod }(12) and \left(\frac{3}{17}\right)=-1 19\equiv 7\text{ mod }(12) and \left(\frac{3}{19}\right)=-1 23\equiv 11\text{ mod }(12) and \left(\frac{3}{23}\right)=1 29\equiv 5\text{ mod }(12) and \left(\frac{3}{29}\right)=-1 31\equiv 7\text{ mod }(12) and \left(\frac{3}{31}\right)=-1 37\equiv 1\text{ mod }(12) and \left(\frac{3}{37}\right)=1 41\equiv 5\text{ mod }(12) and \left(\frac{3}{41}\right)=-1 43\equiv 7\text{ mod }(12) and \left(\frac{3}{43}\right)=-1 47\equiv 11\text{ mod }(12) and \left(\frac{3}{47}\right)=1

Now, if we had to do this prime by prime, it would be horrible.  Instead, we will end up computing all Legendre symbols $\left(\frac{a}{p}\right)$ with $a\neq -1,2$ by reducing them to $\left(\frac{-1}{p}\right)$ or $\left(\frac{2}{p}\right)$ using techniques from last time and the following theorem - parts of which were conjectured and proved by Euler, all of which was conjectured by Legendre, and no fewer than eight proofs of which Carl Friedrich Gauss provided over the course of his lifetime:

Theorem (Quadratic Reciprocity):  If $p$ and $q$ are odd primes not equal to each other, then $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)}\, .$$

You can see from the handout how Legendre thought of this.  Notice also that we can multiply the fractions to rewrite it as $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}\, ,$$ though I like the more symmetric version better.

Example:

We immediately apply this to vastly simplify the calculation we just did.

• Let $q=3$ and $p>3$.
• Since $(3-1)/2=1$, we have $$\left(\frac{3}{p}\right)\left(\frac{p}{3}\right)=(-1)^{(p-1)/2}\text{, or }\left(\frac{3}{p}\right)=(-1)^{(p-1)/2}\left(\frac{p}{3}\right)\, .$$
• Since $1\in Q_3$ and $2\notin Q_3$, the Legendre symbol on the right evaluates like this: $$\left(\frac{p}{3}\right)=1\text{ if }p\equiv 1\text{ mod }(3)\text{ and }\left(\frac{p}{3}\right)=-1\text{ if }p\equiv 2\text{ mod }(3)\, .$$
• Likewise, $$(-1)^{(p-1)/2}=1\text{ if }p\equiv 1\text{ mod }(4)\text{ and }(-1)^{(p-1)/2}=-1\text{ if }p\equiv 3\text{ mod }(4)\, .$$
• Combine these together and we get that $\left(\frac{3}{p}\right)=1$ exactly $$\text{when }p\equiv 1\text{ mod }(3)\text{ and mod }(4)\text{, or when }p\equiv 3\text{ mod }(4)\text{ and }\equiv 2\text{ mod }(3)\; ,$$ which is precisely $p\equiv 1,11\equiv \pm 1$ mod (12) as above!  Amazing.
ls=prime_range(3,50) M=matrix(len(ls),[legendre_symbol(a,b) for a in ls for b in ls]) print block_matrix([0,matrix(1,len(ls),ls),matrix(len(ls),1,ls),M]) ls2 = flatten([0]+[ls]+[[b]+[legendre_symbol(a,b) for a in ls] for b in ls]) N = matrix(len(ls)+1,ls2) show(N)

What does quadratic reciprocity mean?  It means that there is a reciprocating relationship - that usually the above matrix is symmetric, for instance.  We can say it another way.

$$\text{For odd primes }p\text{ and }q,\; \left(\frac{p}{q}\right)= \left(\frac{q}{p}\right)\text{ except when }p\equiv q\equiv 3\text{ mod }(4)$$

It makes computation of Legendre symbols very, very easy if you have a prime factorization of $p$ (and all the intermediate steps).  You just need to use the following facts we already proved, in addition to quadratic reciprocity.

• $\left(\frac{-1}{p}\right)=1\iff p\equiv 1\text{ mod }(4)$
• $\left(\frac{2}{p}\right)=1\iff p\equiv \pm 1\text{ mod }(8)$

Let's look at several examples of how to do this.  For instance:

• $\left(\frac{83}{103}\right)$
• $\left(\frac{219}{383}\right)$

And we can check them, of course.

legendre_symbol(83,103);legendre_symbol(219,383)
 1 1 1 1

We can also come up with congruence criteria like above for other primes.  See the exercises.

What else does quadratic reciprocity do?

Indirectly, it allows us to compute Legendre symbols $(\frac{a}{p})$ without factoring $p$.

Definition:

Let $n$ be an odd number which factors as $$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\; .$$ Then the Jacobi symbol $\left(\frac{a}{n}\right)$ is just the product of the relevant Legendre symbols, $$\left(\frac{a}{n}\right)=\left(\frac{a}{p_1}\right)^{e_1}\left(\frac{a}{p_2}\right)^{p_2}\cdots \left(\frac{a}{p_k}\right)^{e_k}$$

Amazingly, the Jacobi symbol has all the same properties the Legendre symbol has - even quadratic reciprocity and the values for $a=-1,2$.  And if $$\left(\frac{a}{n}\right)=-1$$ then $a$ is not a QR of $n$.  The only thing not the same is that $$\left(\frac{a}{n}\right)=1 \not\Rightarrow a\text{ is a QR of }n\; .$$ In Sage, this is named after yet another generalization called the Kronecker symbol.

 1 [0, 1, 4, 6, 9, 10] 1 [0, 1, 4, 6, 9, 10]

The point of this is not to use the definition of the Jacobi symbol to do anything.  That would be pointless.

The idea is that you can use the Jacobi symbol to do your calculation of Legendre symbols!  After all, they follow almost all the same rules.  You'd only need to factor here in order to make sure you don't have an even number in the denominator of the symbol.

It turns out that, unlike factoring (as far as we know), this leads to an algorithm which needs only about the square of the number of digits of $p$ steps to evaluate the symbol, which is much better than one would need if one had to factor first!

Some examples would be just as fast doing it either way, like $\left(\frac{83}{103}\right)$.  But others would be much slower, because you'd have to factor a few different times.  Here's an example; note that $943$ is not prime.  $$\left(\frac{943}{997}\right)=\left(\frac{997}{943}\right)\text{ since }997\equiv 1\text{ mod }(4)$$ $$=\left(\frac{54}{943}\right)=\left(\frac{2}{943}\right)\left(\frac{27}{943}\right)=(+1)\left(\frac{27}{943}\right)\text{ since }943\equiv -1\text{ mod }(8)$$ $$=-\left(\frac{943}{27}\right)\text{ since both are }\equiv 3\text{ mod }(4)$$ $$=-\left(\frac{25}{27}\right)=-1\text{ because }25=5^2$$  And we can check this out with Sage:

kronecker_symbol(943,997)
 -1 -1

Compare this with having to first factor $943$ and then still do the whole reciprocity dance, and this is much easier and more automatic for a computer to do.  (By the way, $943=23\cdot 41$ - not a gimme.)

What else can quadratic reciprocity do?

It can help us with factoring large integers $n$; Gauss did this.  The process itself is just a little too long to make it worth including here, but it's important to get the flavor.

The essential idea is that if $a$ is a QR of $n$, then $a$ is a QR of any prime $p\mid n$.  So since QRs often have congruence conditions associated with them, $n$ must obey all of the congruence conditions for $\left(\frac{a}{p}\right)$ for all the $p$ which divide it.

Then we can use a variant on the Fermat factoring method to check for possible $a$ for which a prime divisor $p$ of $n$ definitely is or definitely is not a QR (which quadratic reciprocity can help with), and then one can compute Legendre/Jacobi symbols of possible $p\mid n$ to reduce to just having to check a very few bigger possible prime factors.

What else can quadratic reciprocity do for us?

It can help us check primality.  One specific place where it is helpful (though not the only one!) is with the so-called Fermat numbers.  Recall that Euler blasted the following conjecture of Fermat's out of the water: $$F_n=2^{2^n}+1\text{ is always prime for }n\geq 0\, .$$  But what about bigger ones - surely they are inaccessible to the usual factoring techniques?  Just like with Mersenne numbers, for which the Lucas-Lehmer test can check for primality (remember GIMPS?), there is a test called Pepin's test which can check for primality of Fermat numbers.  (Pepin did this work in the late 1800s.)  It turns out that no bigger Fermat numbers have turned out to be prime (all the way through $n=31$); see here, part of the excellent Prime Pages, for more information.

Here is the test in Sage:

@interact def _(n=(1,[1..6])): F=2^(2^n)+1 html("The $%s$th Fermat number is $%s$"%(n,F)) test = mod(3,F)^((F-1)/2) if test == -1: html("Since $3^{(%s-1)/2}\equiv %s$, this Fermat number is prime"%(F,test)) else: html("Since $3^{(%s-1)/2}\equiv %s$, this Fermat number is not prime"%(F,test))

Click to the left again to hide and once more to show the dynamic interactive window

Or, you can write it as:  $$F_n=2^{2^n}+1\text{ is prime exactly when }3^{2^{2^n-1}}\equiv -1\text{ mod }2^{2^n}+1\, .$$  This is really Euler's criterion for checking whether 3 is a quadratic residue mod $F_n$, and getting a negative answer.  (Notice that it is not very helpful for $n=0$, which is why we skip that.)

Why would this check for primality?

Proof:

• First, let's assume $F_n$ is prime.
• Since $F_n$ is one more than a multiple of four, it is clearly $$F_n\equiv 1, 5,\text{ or }9\text{ mod }(12)\; .$$
• If $F_n\equiv 1\text{ mod }(12)$, then $3\mid 2^{2^n}=F_n-1$, which cannot be true.
• If $F_n\equiv 9\text{ mod }(12)$, then $F_n$ is a number greater than three which is divisible by three - but it's prime, so that's not possible.
• So $F_n\equiv 5\text{ mod }(12).$  That means $3\notin Q_p$, based on our work earlier today.
• So if $F_n$ is prime, then Euler's criterion gives the result.
• Now let's assume that Euler's criterion gives this answer of $-1$.
• Then square both sides to get $$3^{F_n-1}\equiv 1\text{ mod }(p)$$ for all primes $p$ dividing $F_n$.
• Since $F_n-1=2^{2^n}$, that means 3 has order (in $U_p$) some power of $2$.
• But 3 can't have order $2^{2^n-1}$ (or less), because it isn't the identity when taken to that power.
• So it must have order $2^{2^n}$.
• But the only way 3 can have that big of an order is if $p$ is at least $2^{2^n}+1$!
• So since $p\mid F_n$, we must have $p=F_n$!

Jones and Jones point out that the proof itself shows that $3$ is a primitive root for $F_n$ if it's prime.  So if we had infinitely many Fermat primes (and not just five of them), we'd have a proof of at least one explicit case for Artin's conjecture (remember that?).  Currently there are none known.

@interact def _(n=(1,[1..6])): F = 2^(2^n)+1 a = mod(3,F) if a.multiplicative_order()==F-1: html("$3$ is a primitive root of $F_{%s}=%s$"%(n,F)) else: html("Not prime, no primitive root!")

Click to the left again to hide and once more to show the dynamic interactive window

So if only Euler had lived another 100 years or so, he wouldn't have needed to do the Great Theorem in Dunham's book where he found that 4294967297 was composite...

Sidelight:

We can use these ideas to find another possible way to attack Artin's Conjecture, by the way.  It's not directly related to the reciprocity per se, but definitely connects all our theoretical ideas of the last two months, and proves something you verified in the take-home.

• Exercise: If $q$ and $p=2q+1$ are both odd primes, then every residue for which primitive root makes sense (i.e. not $a=-1$ or $a=0$) is either a primitive root or a QR.
• Such a prime $p$ must be of the form $p\equiv 3\text{ mod }(4)$, because $q=2k+1$ so that $$p=2(2k+1)+1=4k+3\; .$$
• Exercise: Not only are all residues either a primitive root or a QR, but $a$ is one of these things precisely when $p-a$ is the other kind.
• Exercise: We know that $$1^2,2^2,3^2,\ldots,q^2$$ are all different modulo $p$, and of course all of these are QRs (and so not primitive roots).
• That means that $p-k^2$, for $2\leq k\leq q$, is a primitive root.
• So we see that $p-4$ is a primitive root for any such prime $p=2q+1$!

So if there were infinitely many Germain primes, we would also have an explicit example of Artin's conjecture... but, so far, no such luck.  The largest currently known Germain prime, due to Tom Wu, is $$183027\cdot 2^{265440}-1$$ - a nearly eighty-thousand digit number.

@interact def _(q=(11,[r for r in prime_range(3,100) if is_prime(2*r+1)])): p = 2*q+1 a=mod(p-4,p) if a.multiplicative_order()==p-1: html("$-4$ is a primitive root of $%s$"%p) else: html("Mistake!")

Click to the left again to hide and once more to show the dynamic interactive window

Next time we will prove quadratic reciprocity, hear a presentation, and then perhaps move on in one of several ways.

Homework:

1. Evaluate all Legendre symbols for $p=7$ using Euler's Criterion.
2. Evaluate the Legendre symbols for $p=11$ and $a=2,3,5$ using the calculation of Eisenstein's we used at the beginning.
3. Use the previous problem, your knowledge of $\left(\frac{-1}{11}\right)$ and of perfect squares to evaluate the other Legendre symbols for $p=11$.
4. Use the Eisenstein calculation to reprove the mod (8) criterion for $\left(\frac{2}{p}\right)$.
5. Make up several hard-looking Legendre symbols $\left(\frac{a}{29}\right)$ (modulo $p=29$) that are easy to solve by adding $p$ or by factoring $a$.
6. Use the multiplicative property of the Legendre symbol to give a congruence condition for when $$\left(\frac{-2}{p}\right)=\pm 1\; .$$
7. Use the previous problem to determine whether there is a solution to $$2x^2-12x+20\equiv 0\text{ mod }(29)\; .$$
8. For $0<a,b<p$, prove that at least one of $a,b,$ and $ab$ is a quadratic residue of $p$.
9. Prove that if $\left(\frac{2}{n}\right)$ is the Jacobi symbol instead of the Legendre symbol, it is still true that it $=1$ precisely when $n\equiv \pm 1\text{ mod }(8)$.  (Remember, $n$ has to be odd by definition.)
10. Prove that for any prime $p$, if $1<i,j<\frac{p}{2}$ and $i\neq j$, then $i^2\not\equiv j^2$ mod ($p$).  (Hint: factor!)
11. Last class we conjectured and proved that $$\sum_{a=1}^{p-1}\left(\frac{a}{p}\right)=0\, .$$  Conjecture (and, if you can, prove) a similar result for $$\sum_{a\in Q_p} a\, .$$
12. Prove: if $p\equiv 3$ mod (4), and if $a\not\equiv \pm 1,0$, then $a$ is a QR if and only if $p-a$ is not a QR.
13. Verify the previous exercise for $p=23$.
14. Let $p$ be a prime of the form $p=2q+1$, where $q$ is prime (recall that $q$ is called a Germain prime in this case).  Show that every residue from 1 to $p-2$ is either a primitive root of $p$ or a quadratic residue.  (Hint: How many possible orders can an element of $U_p$ can have?)
15. Show that if $p$ is an odd prime, then there are exactly $\frac{p-1}{2}-\phi(p-1)$ residues which are neither QRs nor primitive roots. (Hint: don't think too hard - just do the obvious counting up.)
16. Evaluate five non-obvious Legendre symbols $(\frac{a}{p})$ for $p=47$ using quadratic reciprocity.
17. Find congruence criteria for $p$ for when $a\in Q_p$ for $a=-3,6$, and $9$. (Hint: Don't do any extra work - use what you know!)

Appendix:

We can also calculate these things using the Gauss Lemma.  Recall that it says that we can tell whether a number $a$ has a square root modulo $p$ simply by checking whether a certain set has even or odd cardinality.  The set was $aP\cup N$, where $P=\{1,2,\ldots ,\frac{p-1}{2}\}$.

One can also use this to prove quadratic reciprocity.   Here, I will just give an argument evaluating $\left(\frac{3}{p}\right)$ for odd primes $p$ using this Gauss Lemma, but somewhat in the style of our integer-point counting of this semester.

In this case, we care about $|3P\cap N|$.  Given $p$, we have that $3P=\{3,6,9,\ldots,\frac{p-1}{2}\cdot 3\}$, and since $\frac{p-1}{2}\cdot 3<\frac{3p}{2}$, the only elements of $3P$ which end up in $N$ are the ones which lie between $\frac{p}{2}$ and $p$ (there aren't any which are in $N$ which wrap around to being between $\frac{3p}{2}$ and $2p$, that is).  So we make this formal - $3P\cap N$ is the set of numbers $3k$ such that $$\frac{p}{2}\leq 3k\leq p\,$$ and its cardinality is the same as the set of numbers $k$ such that $$\frac{p}{6}\leq k\leq \frac{p}{3}\, .$$  (Actually, we only care about the parity of the cardinality of this set.)

Now suppose that during experimentation I already discovered that the residue of $p$ mod (12) seemed to control whether $3$ was a QR mod ($p$).  Then I might as well try writing $p=12m+r$ for some $r\in \{1,5,7,11\}$.  If so, then we are looking for the parity of the set of $k$ such that $$\frac{12m+r}{6}\leq k\leq \frac{12m+r}{3}\Rightarrow 2m+\frac{r}{6}\leq k\leq 4m+\frac{r}{3}\Rightarrow \frac{r}{6}\leq k\leq 2m+\frac{r}{3}\, .$$  Now comes something tricky; since we are looking for the parity, the set of $k$ such that $\frac{r}{3}<k\leq 2m+\frac{r}{3}$ will not be relevant - it leaves the parity alone.  So I can finally say I am looking for the parity of $$\frac{r}{6}\leq k\leq \frac{r}{3}\, .$$  As we mentioned above, the possibilities are $r=\{1,5,7,11\}$; for $r=1$ there are of course no such $k$, and for $r=11$ we get both $k=2$ and $k=3$, so if $r\equiv \pm 1$, the parity is even.  On othe other hand, for $r=5$ we get $k=1$, and for $r=7$ we get $k=2$, so both of these sets have odd parity.  That means:

• $\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)

In case that all seemed too weird:

p=31 [3*x for x in [1..(p-1)/2] if ((3*x)%p)>(p-1)/2]
 [18, 21, 24, 27, 30] [18, 21, 24, 27, 30]
r=p%12 [x for x in [1..(r/3)] if x>=(r/6)]
 [2] [2]
[x for x in [1..(p/3)] if x>(p/6)]
 [6, 7, 8, 9, 10] [6, 7, 8, 9, 10]

Notice that by ignoring the $k$ such that $\frac{r}{3}<k\leq 2m+\frac{r}{3}$, we kept parity (and got $k=2$ as I predicted above).  And:

legendre_symbol(3,31)
 -1 -1