# MAT 338 Day 9 2011

## 3339 days ago by kcrisman

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.

@interact(layout=[['p','a']]) def _(p=(7,prime_range(50)),a=(3,[0..50])): b=mod(a,p) top=ceil(2*p/10)*10 html("If we look at some of the powers of $%s$"%(a,)) html("modulo the prime $%s$, we get:"%(p,)) html("<ul>") for m in [0..top]: html("<li>$%s^{%s}\equiv %s\\text{ mod }(%s)"%(a,m,b^m,p)) html("</ul>") ## 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 super-cool. It puts all the same information in one, short, color-coded format. The$a-1$row and$b$column gives the color corresponding to$(a-1)^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. @interact def power_table_plot(p=(7,prime_range(50))): P=matrix_plot(matrix(p-1,[mod(a,p)^b for a in range(1,p) for b in srange(p)]),cmap='Oranges') show(P) ## 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! import matplotlib.cm; matplotlib.cm.datad.keys() 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? @interact def addition_table_(p=(11,prime_range(50))): P=matrix(p,[mod(a,p)+mod(b,p) for a in [0..p-1] for b in [0..p-1]]) html("<p>The addition table for prime %s</p>"%(p,)) show(P) ## 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]\}$. @interact def _(p=(11,prime_range(10,50))): P=matrix(p,[mod(a,p)*mod(b,p) for a in [0..p-1] for b in [0..p-1]]) html("<p>The multiplication table for prime %s</p>"%(p,)) show(P) ## 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. • 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 - 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.) Remember, we can get this with the following command. inverse_mod(26,31)  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. c = mod(26,31) c^-1  6 6 c*c^-1  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!" @interact def multiplication_table_plot(p=(7,prime_range(50))): P=matrix_plot(matrix(p,[mod(a,p)*mod(b,p) for a in srange(p) for b in srange(p)]),cmap='jet') show(P) ## 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$(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 $$(p-1)!\equiv1\cdot 2\cdot 3\cdots (p-2)\cdot (p-1) \equiv 1 \cdot a\cdot a^{-1}\cdot b\cdot b^{-1}\cdots (p-1)\equiv 1\cdot 1\cdot 1\cdots 1\cdot (p-1)\equiv (p-1)\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 (a-1)(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 p-1$, 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! @interact def _(p=(13,prime_range(10,100))): html("Values of$x^2+1$mod %s"%(p,)) html("<ul>") for m in [0..p-1]: html("<li>$%s^2+1\equiv %s\\text{ mod }(%s)$"%(m,mod(m,p)^2+1,p)) html("</ul>") ## 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^2-1\equiv 0$mod ($n$) )? This is quite tricky, but you will see some patterns. @interact def _(n=(12,[10..100])): html("Values of$x^2-1$mod %s"%(n,)) html("<ul>") for m in [0..n]: html("<li>$%s^2-1\equiv %s\\text{ mod }(%s)$"%(m,mod(m,n)^2-1,n)) html("</ul>") ## 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! 1. Solve: •$18x\equiv 42$mod ($50$) •$6x\equiv 3$mod ($9$) •$980x \equiv 1540$mod ($1600$) 2. When eggs in a basket are removed two, three, four, five, or six at a time, there remain, respectively, one, two, three, four, or five eggs. When they are taken out seven at a time, none are left over. Find the smallest number of eggs that could have been contained in the basket. (Brahmagupta, 7th century AD) 3. Find an integer that leaves a remainder of 9 when it is divided by either 10 or 11, but that is divisible by 13. 4. Show that the system of congruences $$x\equiv a\text{ mod }(m)$$ $$x\equiv b\text{ mod }(n)$$ has a solution precisely if$gcd(m,n)|(a-b)$. 5. Use our conjectured theorem about$a^{p-1}$mod ($p$) to help you calculate each of the following very quickly: •$512^{372}$mod (13) •$3444^{3233}$mod (17) •$123^{456}$mod (23) 6. Write out the multiplication table for$\mathbb{Z}_7$completely, by hand. 7. Show that Wilson's Theorem fails for$p=10$and check that it works for$p=11$by hand. 8. Do exploration to try to find a criterion for which primes$p$there are square roots of$-1$. You will have to examine primes less than 10 by hand to make sure you are right! 9. Do exploration to find out anything you can about how many square roots of$1$there are for a given$n$. 10. Prove our conjectured theorem that$a^{p-1}\equiv 1$mod ($p$), in three steps: • Prove: If$gcd(a,p)=1$and$p$is prime, show that$\{a,2a,3a,\ldots,(p-1)a,pa\}$is a complete residue system mod ($p$). That is, show that the set$\{[a],[2a],[3a],\ldots,[pa]\}$is the whole set$\{[0],[1],[2],\ldots,[p-1]\}$, though of course in a different order! • Prove: If$p$is prime and$p$does not divide$a\$, then $$a\cdot 2a\cdot 3a\cdots (p-1)a\equiv 1\cdot 2\cdot 3\cdots (p-1)\text{ mod }(p)\, .$$
• Use these (with or without Wilson's Theorem) to finish the proof.