All published worksheets from http://sagenb.org
Image: ubuntu2004
MATTHEWWWWWW BATEMANNNNNNN
Math 356: Number Theory
Fall 2011, Willamette University
Sage Investigation 1: The Euler Phi Function and Modular Congruence
Using Sage, we can quickly investigate some patterns related to modular congruence. This worksheet is designed to help you explore the Euler phi function , and to develop some conjectures regarding its value and its relation to modular congruence.
Assignment goals:
- To experience what it is like to be a Number Theorist, exploring patterns, making conjectures, and proving cool things.
- Secure our knowledge of some key theorems by discovering them for ourselves
- Practice using sage (which has become a valuable tool in modern mathematics for developing and testing conjectures)
Task 0: Using this worksheet
To edit this worksheet, you need to open an account at http://www.sagenb.org/. You can create an account by clicking the 'log in to edit a copy' link in the left hand corner. Once you have an account, you can then 'edit a copy' of this worksheet and save it to your worksheets library. When you are done, turn in a print out of your sws file.
Here are a few basic facts about sage. To create a new calculation box move the cursor until a blue line appears and click. To creat a text box (in which to write down conjectures or notes), again move the cursor until a blue line appears, but hold down the shift key while clicking. You can double click on text to edit the text box, or click once on a calculation box to edit the code. After you have edited the code, click the evaluate link. You can enter LaTeX code in the text box. Exotic code requiring non-standard packages may not work, but your standard LaTeX code works fine. How cool is that?!? (Hypothetical question - it's clearly very cool!)
Task 1: Open a new text box at the very top of this worksheet and enter your name.
The Euler Phi Function
Sage has a plethora of useful number theory functions. Today, we'll be exploring its Euler phi (or totient) function and its modular arithmetic features. The window below demonstrates how to calculate the Euler phi function of an integer n. Note: lines preceeded by a # sign are comments, not executed sage code.
So there are 4 integers less than 5 and greater than 0 which are relatively prime to five (namely 1, 2, 3, and 4).
Task 2: Fill in the following: For any prime ,
What is for any prime p? Below are a few calculations. Try some more until you feel you have established the formula for . Once you think you know the general formula, enter it into the Task 3 line below (double click on Task 3 to make changes).
Task 3:
Optional Task 3b: Prove your general form for is correct. We'll be going over this in class.
Now lets investigate for positive integers and . Below are a few sample calculations. Try some more until you feel you have established the general formula.
Task 4:
Modular Congruence Theorem
The Euler phi function is key to one of the most spectacular theorems regarding modular congruence. This theorem is important not only for its beauty, but for its sublime utility in modern cryptography. Use the following calculations, and more of your own if necessary, to deduce this remakable theorem.
First, let us go over a few useful modular arithmetic functions.
Now let us examine the powers of [a] in Z/nZ
Let us start with Z/5Z.
Clearly $[1]^i=[1][0]^i=[0]$ for all in Z. What about [2], [3], and [4]? And while we're at it, lets look at an example of using for loops in sage.
Interesting! for all in Z/5Z. Lets look at the powers of in Z/9Z. Recall Z/9Z=.
Hmm, hard to see a pattern yet. Are there any values of for which for all in Z/9Z? No, but the results for are interesting. We see they are all except for and .
Questions to ponder:
- What is a signifficant difference between and ? (5 is prime, 9 is not)
- Is there a difference between the sets of numbers and in relation to the number 9? Similarly, is there a way in which are related to in the same manner that are related to 9? (3 and 6 share divisors, whereas 1,2,4,5,7,8 are relatively prime to 9 - same with the set denoted for 5)
- Can you find a relationship that relates to in the same way that is related to ?
Task 5: Experiment more below, calculating the powers of the equivalence classes for Z/nZ for at least 2 more value of n.
I've included a few other sage functions in the appendix below related to concepts we've already covered in class. These may or may not be useful to you in your experimentation.
I think you're ready. Can you identify one of the most spectacular theorems regarding modular congruence? I'll give you a hint. It's of the form
Thm: for all (maybe?)
Task 6: Fill in the statement of the above theorem.
Appendix 1: Some Useful Sage Functions Related to Modular Equivalence, GCD, Primes, and Factorization