We have the opportunity now just to answer one or two questions on doing the CRT things. Otherwise$\ldots$
Today is a great day! We get to explore, explore, explore  and hopefully to prove, just a bit.
Click to the left again to hide and once more to show the dynamic interactive window 
Did you get a chance to come up with something? What do you think? Did you come up with some potential theorems?
This next interact is supercool. It puts all the same information in one, short, colorcoded format. The $a1$ row and $b$ column gives the color corresponding to $(a1)^b$ mod ($p$). That means the first ($0$th) column is the color for $1$ and the second ($1$th) column gives the colors of each element of $\mathbb{Z}_p$. For instance, $(3,4)$ corresponds to $2^4$ mod ($7$) in the initial example below.
Click to the left again to hide and once more to show the dynamic interactive window 
What possible theorems can you see here?
Note that if you don't like the colors, you can change the word in the quotes after the word 'cmap'; if you get rid of that, it will be a grayscale plot. Some others you could try are 'Oranges' or 'hsv' or $\ldots$  well, see the cell below this one if you REALLY want to know!

We're going to sort of think about this until we come up with some nice theorem regarding whether there are any patterns in $a^b$ mod ($p$) that hold for all $p$ or all $a$ or all $b$ or some of these.
In the meantime, let's introduce ourselves to $\mathbb{Z}_p$! After all, this friendly number system will become a good acquaintance, if not friend, throughout the rest of the course.
As it turns out, $\mathbb{Z}_p$ has several very interesting properties. Like all of our number systems in this class, you can add and multiply elements of $\mathbb{Z}_p$ (we call something like that a ring).
We can make an addition table, for instance. This is not very interesting. But in some sense, it is interesting that it isn't interesting. Does that make any sense?
Click to the left again to hide and once more to show the dynamic interactive window 
Next, the multiplication table. Notice that this is a little more interesting. Most importantly, notice that the columns and rows are both from 0 to $p1$; this is standard. Until we hit Chapter 7, we'll usually just use the set of least nonnegative residues to represent $\mathbb{Z}_p$  that is, $\{[0],[1],[2],\ldots,[p2],[p1]\}$.
Click to the left again to hide and once more to show the dynamic interactive window 
One interesting part of this is that every row and every column (other than the ones corresponding to 0) has the entry $1$ in it. You can't necessarily say this about other numbers. This corresponds to a corollary of something we used last time.
(This means it is a field  another example of bizarre but fun math nomenclature.)
Remember, we can get this with the following command.
6 6 
It turns out there is an even easier way to get at this in Sage than the one I used last time! In retrospect, it makes sense.
6 6 
1 1 
What's even better is to see this visually! I still can't get over how easy it is for me to do this in Sage (and other math programs); it is so cool that even my wife said, "What's that  it's neat!"
Click to the left again to hide and once more to show the dynamic interactive window 
We will be doing quite a bit with all this. Come up with any patterns yet?
Here is one little fact I won't try to have us guess  and I'll give you the proof right away, too:
Wilson's Theorem: If $p$ is a prime, then $(p1)!\equiv 1$ mod ($p$).
Proof: If $p=2$ this is very, very easy to check. So assume $p\neq 2$, hence $p1$ is even. For each $n$ such that $1 < n < p1$, we know that $n$ has a unique inverse modulo $p$. Pair up all the numbers between 1 and $p1$ in this manner; for instance, if $p=7$, then we can do $(5,3)$ and $(4,2)$. Then multiplying out $(p1)$ factorial, we get $$(p1)!\equiv1\cdot 2\cdot 3\cdots (p2)\cdot (p1) \equiv 1 \cdot a\cdot a^{1}\cdot b\cdot b^{1}\cdots (p1)\equiv 1\cdot 1\cdot 1\cdots 1\cdot (p1)\equiv (p1)\equiv 1\text{ mod }(p)$$ The only loose end is that perhaps some number pairs up with itself, which would mess up that all the numbers pair off nicely. However, in that case, $a^2\equiv 1$ mod ($p$), so by definition $p\mid (a1)(a+1)$; since $p$ is prime, it must divide one or the other of these factors, and in either case $a\equiv 1$ or $a\equiv p1$, which are not the numbers pairing off.
We are slowly moving on, somewhat in parallel with the book but pursuing our own ends. We have pretty much exhausted what we want to do with linear congruences, and it is time to start moving on to higher degree congruences.
Just as in high school algebra one moved from linear functions to quadratics (and found there was a LOT to say about them!), this is the next natural step in number theory. We haven't abandoned integers, by the way! But it turns out that the questions about quadratic polynomials with integers are much, much harder, and are better pursued after studying the relatively simple (and computable) cases of quadratic congruences. After Spring Break we will return to a full investigation of this; for now we will look for patterns in two questions. Namely:
For what prime $p$ does $1$ have a square root? That is, is there a solution to $x^2\equiv 1$ mod ($p$), or $x^2+1\equiv 0$ mod ($p$)? This interact is designed to help answer this  as well as how many square roots $1$ has when they exist!
Click to the left again to hide and once more to show the dynamic interactive window 
The interact below helps answer a similar question; for what integers $n$ does $1$ have more square roots than just $\pm 1$? That is, how many solutions to $x^2\equiv 1$ mod ($n$) are there (equivalently, to $x^21\equiv 0$ mod ($n$) )? This is quite tricky, but you will see some patterns.
Click to the left again to hide and once more to show the dynamic interactive window 
Homework for Monday  BUT I expect that you have already done and written the last three for Friday's class!
