We can actually completely calculate $\left(\frac{2}{p}\right)$ with Euler's Criterion to prove that our conjecture from above is right, that
We will try to show this by writing $(p1)!$ in two different ways.
Proving the general case basically follows this to its natural conclusion; there was nothing special in the above argument about $p=11$.
Click to the left again to hide and once more to show the dynamic interactive window 
Let's try to calculate some Legendre symbols. Remember, we have several interesting properties, including a sort of multiplicativity and Euler's criterion. We proved this last time.
Proposition: If $n=ab$ is a factorization (not necessarily nontrivial) of $n$, then $n$ is a QR of $p$ precisely when either both $a$ and $b$ are QRs of $p$ or both $a$ and $b$ are not Rs of $p$. (Hence if one of $a,b$ is and the other isn't, neither is $n$.)
In terms of Legendre symbols, it means $$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$
It is also true that $x^2\equiv a$ mod ($n$) if and only if $x^2\equiv a+n$ mod ($n$), which means that we can look at whatever residue of $a$ is convenient, or $$\left(\frac{a+p}{p}\right)=\left(\frac{a}{p}\right)$$ Now let's try this.
It turns out you can resolve theoretical questions this way too.
Thus we see that calculation and theory must go hand in hand; they are not separate. Now, what I did in using the Euler Criterion (EC) to find $\left(\frac{2}{p}\right)$ was to look at numbers like $2x$. So one might ask whether something like this calculation could work with general $a$ and numbers like $ax$ to find a better theoretical result.

It turns out that this is true. We are going to follow the steps of Gauss' protege Eisenstein here (see the appendix for how Gauss did it). Eisenstein was yet another brilliant young mathematician who came out of nowhere but died young because he couldn't find a job which could help his chronic illness, like Abel (and probably like Galois would have done, due to his hotheadedness, if he hadn't been killed in a duel first).
We are going to try to find a different way to evaluate $\left(\frac{a}{p}\right)$ than using Euler's criterion, for $p$ an odd prime and $gcd(a,p)=1$.
First, let's introduce a new set and look at a couple properties.
Now let's try to get something like in Euler's criterion.
So we have reduced evaluating the Legendre symbol (and hence deciding whether things have square roots modulo $p$) to the parity of a certain sum; hopefully that's an improvement on taking powers. Of course, it's still somewhat unwieldy, so there is a final simplification.

Now, you might think we have to keep doing this, and that our task of finding out when numbers have square roots mod ($p$) is hopeless! But quite the opposite is true  and next time we will derive the same result almost effortlessly using the great theorem called quadratic reciprocity!
Homework:
Appendix
In fact, it turns out that there is a different refinement of the Euler Criterion which can help us evaluate Legendre symbols without taking powers of $a$ at all. We only have to check whether a certain set has even or odd cardinality. The definition of the set is annoying, though, so here we go.
Let $p$ be an odd prime, so that $\frac{p1}{2}$ and $\frac{p+1}{2}$ are consecutive integers which sort of divide the set of nonnegative residues in half. Then we define, for a given integer $a$, the following four sets:
As the book points out, $N$ is a special case of $aP$, for $a=1$. Try writing out $2P$ for $p=11$ right now, as well as try to find the sets $2P\cap N$ and $2N\cap P$. Example 7.7 on page 127 also does this. We can do another example if that would help clear up what the four sets above are, as well as how to calculate their intersections (when nonempty).

set([8, 10, 6]) set([8, 10, 6]) 
As you can see, Sage can do this with some annoying syntax you might as well avoid.
Okay, now let's start multiplying. First off, let's multiply everything in $aP$ and factor out all the $a$s: $$a(2a)(3a)\cdots (\frac{p1}{2}a)= a^{(p1)/2}\left(\frac{p1}{2}\right)!$$ Now, the Euler Criterion says that $$a^{(p1)/2}\left(\frac{p1}{2}\right)!\equiv \left(\frac{a}{p}\right)\left(\frac{p1}{2}\right)!\text{ mod }(p)\, .$$ So let's see if we can write the product of everything in $aP$ some other way in order to cancel out the factorial, since that would evaluate $\left(\frac{a}{p}\right)$, right? At this point we are going to use the same trick I used above with the multiples of 2  I am going to factor out a $1$ from exactly the right pieces of the product $a(2a)(3a)\cdots (\frac{p1}{2}a)$.
First off, note that for any relevant integer $x$, $x$ and $x$ are in opposite pieces $aP$ and $aN$. This is because if $x\equiv am\in aP$ and $x\equiv an\in aP$ (so that $0<m,n<\frac{p1}{2}$), then $$0=x+(x)\equiv am+an=a(m+n)\text{ mod }(p)\, .$$ So since $p$ doesn't divide $a$, it must divide $m+n$, but we just said that $0<m,n<\frac{p1}{2}$, which means $0<m+n<p$  a contradiction.
But that means that if I factor out $1$ from some element of $aP$ which is also in $N$ (e.g. if $ax=(1)n$ for some $n\in P$), then the result is actually not in $aP$, but is now in $P$ (so it is a least positive absolute residue, e.g. $0<n<\frac{p}{2}$). So if we factor out $1$ from all the elements of $aP$ which are also in $N$, we will have every single element of $P$ in the product again! This is a little tough to digest, but it is the crux of the argument.
Once we believe the last paragraph, that means $$a(2a)(3a)\cdots (\frac{p1}{2}a)\equiv (1)^{aP\cap N}\left(\frac{p1}{2}\right)!$$ Now we combine it with the other evaluation of the product of all the elements of $aP$: $$\left(\frac{a}{p}\right)\left(\frac{p1}{2}\right)!=a(2a)(3a)\cdots (\frac{p1}{2}a)\equiv (1)^{aP\cap N}\left(\frac{p1}{2}\right)!\text{ mod }(p)$$ and we cancel out the factorials, getting $$\left(\frac{a}{p}\right)=(1)^{aP\cap N}\text{  the Gauss Lemma, as it is called.}$$
3 3 
Again, weird Sage syntax gives us the correct answer of $\left(\frac{2}{11}\right)=(1)^{2P\cap N}=(1)^3=1$, which we already knew since $11\equiv 3$ mod (4).
But now we have a VERY powerful tool for evaluating lots of Legendre symbols at once. I encourage you to read how Jones and Jones evaluate $\left(\frac{2}{p}\right)$ using the Gauss Lemma in Corollary 7.10, and to compare it to how I did it at the beginning of this lecture. It also will enable us to prove the extremely powerful theorem of Gauss' we will discuss next time.
[(13, 1), (11, 1), (5, 1), (7, 1)] [(13, 1), (11, 1), (5, 1), (7, 1)] 
