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?
This next interact is super-cool. The rows are labeled with a-1, unfortunately - so row 3 corresponds to a=4 - but the columns are the actual powers b. The first row is the powers of 1, so everything is the same - all powers of 1 are the same! The first column likewise is a^0 for all non-zero elements, so that will also all be the same. The second column, on the other hand, shows you the colors which correspond to all the different numbers in \mathbb{Z}_p.
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!
Click to the left again to hide and once more to show the dynamic interactive window |
['Spectral', 'summer', 'RdBu', 'gist_earth', 'Set1', 'Set2', 'Set3', 'Dark2', 'hot', 'PuOr_r', 'PuBuGn_r', 'RdPu', 'gist_ncar_r', 'gist_yarg_r', 'Dark2_r', 'YlGnBu', 'RdYlBu', 'hot_r', 'gist_rainbow_r', 'gist_stern', 'cool_r', 'cool', 'gray', 'copper_r', 'Greens_r', 'GnBu', 'gist_ncar', 'spring_r', 'gist_rainbow', 'RdYlBu_r', 'gist_heat_r', 'OrRd_r', 'bone', 'gist_stern_r', 'RdYlGn', 'Pastel2_r', 'spring', 'Accent', 'YlOrRd_r', 'Set2_r', 'PuBu', 'RdGy_r', 'spectral', 'flag_r', 'jet_r', 'RdPu_r', 'gist_yarg', 'BuGn', 'Paired_r', 'hsv_r', 'YlOrRd', 'Greens', 'PRGn', 'gist_heat', 'spectral_r', 'Paired', 'hsv', 'Oranges_r', 'prism_r', 'Pastel2', 'Pastel1_r', 'Pastel1', 'gray_r', 'PuRd_r', 'Spectral_r', 'BuGn_r', 'YlGnBu_r', 'copper', 'gist_earth_r', 'Set3_r', 'OrRd', 'PuBu_r', 'winter_r', 'jet', 'bone_r', 'BuPu', 'Oranges', 'RdYlGn_r', 'PiYG', 'YlGn', 'binary_r', 'gist_gray_r', 'BuPu_r', 'gist_gray', 'flag', 'RdBu_r', 'BrBG', 'Reds', 'summer_r', 'GnBu_r', 'BrBG_r', 'Reds_r', 'RdGy', 'PuRd', 'Accent_r', 'Blues', 'Greys', 'autumn', 'PRGn_r', 'Greys_r', 'pink', 'binary', 'winter', 'pink_r', 'prism', 'YlOrBr', 'Purples_r', 'PiYG_r', 'YlGn_r', 'Blues_r', 'YlOrBr_r', 'Purples', 'autumn_r', 'Set1_r', 'PuOr', 'PuBuGn'] ['Spectral', 'summer', 'RdBu', 'gist_earth', 'Set1', 'Set2', 'Set3', 'Dark2', 'hot', 'PuOr_r', 'PuBuGn_r', 'RdPu', 'gist_ncar_r', 'gist_yarg_r', 'Dark2_r', 'YlGnBu', 'RdYlBu', 'hot_r', 'gist_rainbow_r', 'gist_stern', 'cool_r', 'cool', 'gray', 'copper_r', 'Greens_r', 'GnBu', 'gist_ncar', 'spring_r', 'gist_rainbow', 'RdYlBu_r', 'gist_heat_r', 'OrRd_r', 'bone', 'gist_stern_r', 'RdYlGn', 'Pastel2_r', 'spring', 'Accent', 'YlOrRd_r', 'Set2_r', 'PuBu', 'RdGy_r', 'spectral', 'flag_r', 'jet_r', 'RdPu_r', 'gist_yarg', 'BuGn', 'Paired_r', 'hsv_r', 'YlOrRd', 'Greens', 'PRGn', 'gist_heat', 'spectral_r', 'Paired', 'hsv', 'Oranges_r', 'prism_r', 'Pastel2', 'Pastel1_r', 'Pastel1', 'gray_r', 'PuRd_r', 'Spectral_r', 'BuGn_r', 'YlGnBu_r', 'copper', 'gist_earth_r', 'Set3_r', 'OrRd', 'PuBu_r', 'winter_r', 'jet', 'bone_r', 'BuPu', 'Oranges', 'RdYlGn_r', 'PiYG', 'YlGn', 'binary_r', 'gist_gray_r', 'BuPu_r', 'gist_gray', 'flag', 'RdBu_r', 'BrBG', 'Reds', 'summer_r', 'GnBu_r', 'BrBG_r', 'Reds_r', 'RdGy', 'PuRd', 'Accent_r', 'Blues', 'Greys', 'autumn', 'PRGn_r', 'Greys_r', 'pink', 'binary', 'winter', 'pink_r', 'prism', 'YlOrBr', 'Purples_r', 'PiYG_r', 'YlGn_r', 'Blues_r', 'YlOrBr_r', 'Purples', 'autumn_r', 'Set1_r', 'PuOr', 'PuBuGn'] |
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).
First, addition. 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 p-1; 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,[p-2],[p-1]\}.
Click to the left again to hide and once more to show the dynamic interactive window |
One very important theoretical point is a corollary of Corollary 3.8. That stated that:
If gcd(a,n)=1, then ax\equiv b mod (n) has a unique solution in \mathbb{Z}_n.
So if n=p is prime, then gcd(a,p)=1 all the time, except for a\equiv 0, so if b=1 then we have a unique solution - that is, I am just restating that for prime moduli, every non-zero element has a unique inverse element in \mathbb{Z}_p. (This means it is a field - another example of bizarre but fun math nomenclature.) It turns out there is an even easier way to get at this in Sage than the one I used last time:
6 6 |
1 1 |
You can see this fact in the multiplication tables. Every row and every column has a '1' in it. 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. 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 (p-1)!\equiv -1 mod (p).
Proof: If p=2 this is very, very easy to check. So assume p\neq 2, hence p-1 is even. For each n such that 1 < n < p-1, we know that n has a unique inverse modulo p. Pair up all the numbers between 1 and p-1 in this manner; for instance, if p=7, then we can do (5,3) and (4,2). Then multiplying out (p-1) factorial, we get
Click to the left again to hide and once more to show the dynamic interactive window |
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)? The interact above is designed to help answer this - as well as how many square roots -1 has when they exist!
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^2-1\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. Please bring in this homework written - including the results of any exploration you did and attempts at theorems. However, this one will be graded as to participation, not as a hand-in homework, so trying hard is what I'm asking for, nothing more.
|
|