However, it is not so easy to just find square roots  or even when there is a square root  modulo $p$ in general. To get a flavor for this, our final goal for today is to explore for which $p$ it is true that $x^2\equiv 2$ mod ($p$) has a solution. Or, to put it another way, when does two have a square root modulo $p$? First do some by hand; for what primes up to 20 does $2$ have a square root? Then we'll look at more data below.
Click to the left again to hide and once more to show the dynamic interactive window 
What do you think? Any patterns?
As it turns out, it is quite hard to prove such patterns without the benefit of powerful theoretical machinery. Which means it is hard to even know whether there is a solution to a given congruence without such machinery! That is what the next week will be about.
In fact, it is even hard to conjecture such things for harder cases unless you are quite clever. Euler was one of the first to do so. Here are three links for a very unusual paper of Euler's  one where he included nary a proof, just closely related conjectures to this question!
Next, I have a handout of more tables made by the great ItalianFrench mathematician Lagrange. Lagrange gave proofs of many of the patterns in quadratic forms (what numbers look like $a^2+b^2$, $a^2+2b^2$, etc.) that Fermat and Euler talked about. We already know two of his theorems; if you ever read any science fiction or space stuff that talks about stable places to orbit being called Lagrange points  that's him too. Lagrange was Euler's successor in Berlin after he went back to Russia under the stable (if despotic) regime of Catherine the Great; later he moved to France and was quite influential there.
[0, 1, 2, 4, 8, 9, 13, 15, 16] [0, 1, 2, 4, 8, 9, 13, 15, 16] 
3 3 
Note this last function gives the smallest nonresidue, in case you need it.
One can approach this subject from many vantage points. However, we have the advantage of having developed the basics of groups and primitive roots, which will simplify much of our exposition.
Group theory approach to quadratic residues:
In fact, $Q_p$ is a group!
You might be wondering how this piece of $U_p$ connects to the most important thing we've seen so far about $U_p$. Recall that $U_p$ was cyclic, that it had a generator whose powers gave us all units modulo $p$. We called such an element a primitive root of $p$.
2 2 
So let's compare the primitive root's powers and the quadratic residues. Shouldn't be too hard...
[2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1] [0, 1, 4, 5, 6, 7, 9, 11, 16, 17] [2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1] [0, 1, 4, 5, 6, 7, 9, 11, 16, 17] 
This exemplifies a major fact.
Fact: For odd prime modulus $p$, the quadratic residues are precisely the even powers of a primitive root $g$.
This will turn out to be a fantastically useful theoretical way to find $Q_p$. It will show up in lots of proofy settings.
However, this is a terrible way to actually find quadratic residues for a given $p$, since it involves finding a primitive root and listing lots of powers! We need both theory and practice.
Here is a much easier way. Recall our observation about the middle column in the colorful matrix of powers modulo a prime: $$a^{(p1)/2}\equiv\pm 1\text{ for all }a\text{ not divisible by }p\; .$$ The following extension of this is usually called Euler's Criterion.
Theorem: If $p$ is an odd prime, then for all integers $a$ not a multiple of $p$ the sign of the following determines whether $a$ is a QR; $$a^{(p1)/2}\equiv\pm 1\text{ mod }(p)\, ,$$ with $+1$ if $a$ is a QR, otherwise $1$.
Proof:
Example:
Notice that this immediately gives our old result that $1$ has a square root modulo an odd prime $p$ precisely when $p\equiv 1$ mod (4), because $(1)^{(p1)/2}=+1$ precisely when $(p1)/2$ is even, or $p\equiv 1$ mod (4). That is MUCH easier than our previous adhoc way of doing it!
Using this same idea, we can prove a very nice result about when a composite number is a QR.
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 QRs of $p$. (Hence if one of $a,b$ is and the other isn't, neither is $n$.)
Proof: Modulo $p$, write $a\equiv g^i$ and $b\equiv g^j$ for some $i,j$. Then $n=ab\equiv g^{i+j}$, and $i+j$ is even when $i$ and $j$ have the same parity. Because of our fact about even powers of the primitive root, this is exactly the same thing as the conclusion of the proposition.
Now I can immediately decide that $2\equiv 21$ is not a QR mod (23) by the fact that $1$ is not a QR but 2 is, which we knew before. Likewise, I can immediately decide that $2\equiv 9$ is a QR mod (11) by the fact that neither $1$ nor $2$ is a QR.
[0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] [0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] 
[0, 1, 3, 4, 5, 9] [0, 1, 3, 4, 5, 9] 
Now there is a very convenient way to notate all this, devised by Legendre, which takes advantage of the fact that $a=g^i$ is an even power exactly when $a$ is a QR, and $(1)^i=1$ precisely when $i$ is even (and hence precisely when $a$ is a QR). This is the socalled Legendre symbol. The command in Sage is pretty straightforward.
1 1 
Click to the left again to hide and once more to show the dynamic interactive window 
We write $\left(\frac{a}{p}\right)$ for the Legendre symbol, so e.g. $\left(\frac{1}{p}\right)=1$ for $p$ prime if and only if $p=2$ or $p\equiv 1$ mod (4).
We define the Legendre symbol of $a$ modulo $p$ to be zero if $p\mid a$.
Let's use our usual example to visualize the tension and connection between primitive roots and quadratic residues.
Question: Before looking at it, do you see why a quadratic residue automatically can't be a primitive root?
Click to the left again to hide and once more to show the dynamic interactive window 
Here is another way to view the tension between primitive roots and quadratic residues (which automatically can't be primitive roots; do you see why?). All the residues are the second column (correctly labeled 1), and all the quadratic residues are the colors in the third column (labeled 2 as they are squares). See how that column is symmetric about the middle of the rows, with two of each of the colors appearing. Note that these are the same colors as every other column in a row with a primitive root (the rows with every color represented), though not necessarily in that order. Also notice that the color of the middle column determines whether the color beginning that row shows up in the second column. Weird! Yet true.
Here's a final fun thing. What is the sum of all Legendre symbols for a given prime?
Click to the left again to hide and once more to show the dynamic interactive window 
This is cool, and a nice example of the kind of fun one can have experimenting. What do you think? Do you think we can prove it?

Homework, due Monday:
