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 integerpoint 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(p1)$. Let's do few examples.
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=p1$.
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
To summarize:
Cool!
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{p1}{2}\right)\left(\frac{q1}{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{(p1)(q1)}{4}}\, ,$$ though I like the more symmetric version better.
Example:
We immediately apply this to vastly simplify the calculation we just did.
[ 0 3 5 7 11 13 17 19 23 29 31 37 41 43 47] [+] [ 3 0 1 1 1 1 1 1 1 1 1 1 1 1 1] [ 51 0 1 1 1 1 1 1 1 1 1 1 1 1] [ 7 1 1 0 1 1 1 1 1 1 1 1 1 1 1] [111 1 1 0 1 1 1 1 1 1 1 1 1 1] [13 1 1 1 1 0 1 1 1 1 1 1 1 1 1] [171 1 1 1 1 0 1 1 1 1 1 1 1 1] [19 1 1 1 1 1 1 0 1 1 1 1 1 1 1] [231 1 1 1 1 1 1 0 1 1 1 1 1 1] [291 1 1 1 1 1 1 1 0 1 1 1 1 1] [31 1 1 1 1 1 1 1 1 1 0 1 1 1 1] [37 1 1 1 1 1 1 1 1 1 1 0 1 1 1] [411 1 1 1 1 1 1 1 1 1 1 0 1 1] [43 1 1 1 1 1 1 1 1 1 1 1 1 0 1] [471 1 1 1 1 1 1 1 1 1 1 1 1 0] [ 0 3 5 7 11 13 17 19 23 29 31 37 41 43 47] [+] [ 3 0 1 1 1 1 1 1 1 1 1 1 1 1 1] [ 51 0 1 1 1 1 1 1 1 1 1 1 1 1] [ 7 1 1 0 1 1 1 1 1 1 1 1 1 1 1] [111 1 1 0 1 1 1 1 1 1 1 1 1 1] [13 1 1 1 1 0 1 1 1 1 1 1 1 1 1] [171 1 1 1 1 0 1 1 1 1 1 1 1 1] [19 1 1 1 1 1 1 0 1 1 1 1 1 1 1] [231 1 1 1 1 1 1 0 1 1 1 1 1 1] [291 1 1 1 1 1 1 1 0 1 1 1 1 1] [31 1 1 1 1 1 1 1 1 1 0 1 1 1 1] [37 1 1 1 1 1 1 1 1 1 1 0 1 1 1] [411 1 1 1 1 1 1 1 1 1 1 0 1 1] [43 1 1 1 1 1 1 1 1 1 1 1 1 0 1] [471 1 1 1 1 1 1 1 1 1 1 1 1 0] 
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)$$
What does quadratic reciprocity do?
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.
Let's look at several examples of how to do this. For instance:
And we can check them, of course.
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:
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 socalled 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 LucasLehmer 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:
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^n1}}\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:
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.
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 takehome.
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 eightythousand digit number.
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:

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{p1}{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 integerpoint counting of this semester.
In this case, we care about $3P\cap N$. Given $p$, we have that $3P=\{3,6,9,\ldots,\frac{p1}{2}\cdot 3\}$, and since $\frac{p1}{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:
In case that all seemed too weird:
[18, 21, 24, 27, 30] [18, 21, 24, 27, 30] 
[2] [2] 
[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:
1 1 