MATTHEWWWWWW BATEMANNNNNNN
︡cec3afe5-f1ee-4f79-8405-2bec3dccf282︡{"html": "MATTHEWWWWWW BATEMANNNNNNN
"}︡ ︠8bb6284c-a42a-4c89-aef3-8db4cb5c4d65i︠ %htmlMath 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 $\phi$, and to develop some conjectures regarding its value and its relation to modular congruence.
Assignment goals:
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 $\phi$
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.
︡9fde3e3b-b019-48bf-b6d2-3af949dfea6b︡{"html": "Math 356: Number Theory
\nFall 2011, Willamette University
\nSage Investigation 1: The Euler Phi Function and Modular Congruence
\nUsing Sage, we can quickly investigate some patterns related to modular congruence. This worksheet is designed to help you explore the Euler phi function $\\phi$, and to develop some conjectures regarding its value and its relation to modular congruence. \ufeff
\nAssignment goals:
\nTask 0: Using this worksheet\ufeff
\nTo 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.
\n\n
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!)
\n\n
Task 1: Open a new text box at the very top of this worksheet and enter your name.
\n\n
The Euler Phi Function $\\phi$
\nSage 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.\ufeff
"}︡ ︠50ca0bda-5177-44e6-91a6-27ebb4941dc1︠ # euler_phi(n) returns the number of integers (less than n and greater than zero) which are relatively prime to n. euler_phi(5) ︡3442c817-be20-4239-b1e3-98eef0c1e295︡{"stdout": "4"}︡ ︠39276615-084b-4964-9b85-ecd8703e3fedi︠ %htmlSo 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 $p$, $\phi(p)= p-1$
What is $\phi(p^i)$ for any prime p? Below are a few calculations. Try some more until you feel you have established the formula for $\phi(p^i)$. Once you think you know the general formula, enter it into the Task 3 line below (double click on Task 3 to make changes).
︡7997d72d-c00b-4fca-b080-ceb6bac20985︡{"html": "So there are 4 integers less than 5 and greater than 0 which are relatively prime to five (namely 1, 2, 3, and 4).
\nTask 2: Fill in the following: For any prime $p$, $\\phi(p)= p-1$
\nWhat is $\\phi(p^i)$ for any prime p? Below are a few calculations. Try some more until you feel you have established the formula for $\\phi(p^i)$. Once you think you know the general formula, enter it into the Task 3 line below (double click on Task 3 to make changes).
"}︡ ︠8f6d8ca3-ac3d-467d-a1f6-462081b3c9e9︠ (euler_phi(2^2), euler_phi(2^3), euler_phi(2^4), euler_phi(3^2), euler_phi(3^3), euler_phi(3^4), euler_phi(5^2), euler_phi(5^3), euler_phi(5^4)) ︡17075d12-0197-465a-bd0b-bf5cc582000c︡{"stdout": "(2, 4, 8, 6, 18, 54, 20, 100, 500)"}︡ ︠4992b1ef-e231-4372-830d-5b78c911f9fd︠ # calculating euler_phi(p^i) ︡062c6c82-3680-48f0-97f5-7f3340a69d81︡︡ ︠6b8fe2ba-900a-4fe5-8fe3-95ed908cce31i︠ %htmlTask 3: $\phi(p^i)= p^i - p^{(i-1)}$
Optional Task 3b: Prove your general form for $\phi(p^i)$ is correct. We'll be going over this in class.
Now lets investigate $\phi(mn)$ for positive integers $m$ and $n$. Below are a few sample calculations. Try some more until you feel you have established the general formula.
︡03cdae0d-dab6-45d9-a44b-af71559792f2︡{"html": "Task 3: $\\phi(p^i)= p^i - p^{(i-1)}$
Optional Task 3b: Prove your general form for $\\phi(p^i)$ is correct. We'll be going over this in class.
Now lets investigate $\\phi(mn)$ for positive integers $m$ and $n$. Below are a few sample calculations. Try some more until you feel you have established the general formula.
"}︡ ︠489ca3c5-3ff9-4202-ba1f-219b05b614a4︠ (euler_phi(76), euler_phi(77), euler_phi(78), euler_phi(79), euler_phi(80), euler_phi(69), euler_phi(70), euler_phi(71), euler_phi(72),euler_phi(73), euler_phi(74), euler_phi(75)) ︡a116e6a7-7490-4e01-be87-e9d627621486︡{"stdout": "(36, 60, 24, 78, 32, 44, 24, 70, 24, 72, 36, 40)"}︡ ︠dd994506-b643-436f-9481-e229ab9203b6i︠ %htmlTask 4: $\phi(mn)= \phi(c)= c*\frac{p_{1}-1}{p_{1}}\frac{p_{2}-1}{p_{2}}...\frac{p_{n}-1}{p_{n}}$
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.
︡d05be00c-83dc-4adf-859b-ea9133f98b18︡{"html": "Task 4: $\\phi(mn)= \\phi(c)= c*\\frac{p_{1}-1}{p_{1}}\\frac{p_{2}-1}{p_{2}}...\\frac{p_{n}-1}{p_{n}}$
\n\n
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.
\nFirst, let us go over a few useful modular arithmetic functions.
"}︡ ︠11206081-2d0d-4b69-a01a-82bc083ae3f4︠ # Modular Arithmetic # gives 100 mod 34 Mod(100, 34) ︡a30aa6f1-a497-4c02-828d-a48ee1aca288︡{"stdout": "32"}︡ ︠a5684cd9-cdc8-407b-8901-f9aff244db82︠ # a^n mod m # 2^100 mod 10 = 6 power_mod(2, 100, 10) ︡3cf32365-b03e-4993-aadf-837ac40eabc7︡{"stdout": "6"}︡ ︠70dea3c2-206a-4e93-81c6-76e9fc53c2b2i︠ %htmlNow let us examine the powers of [a] in Z/nZ
Let us start with Z/5Z.
Clearly $[1]^i=[1]$ and $[0]^i=[0]$ for all $i$ 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.
︡a8efa62c-990b-4b6e-b8ff-859c7000ff3f︡{"html": "Now let us examine the powers of [a] in Z/nZ
\nLet us start with Z/5Z\ufeff.
\nClearly $[1]^i=[1]$ and $[0]^i=[0]$ for all $i$ 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.
"}︡ ︠edad3d4f-073c-4112-9bc1-21df22eb83be︠ # a2 will be the vector containing powers of [2], a3 the powers of [3], and a[4] the powers of [4] a2=[]; a3=[]; a4=[]; for i in range(1,5): a2.append(power_mod(2,i,5)) a3.append(power_mod(3,i,5)) a4.append(power_mod(4,i,5)) print "Powers of [2]=",a2 print "Powers of [3]=",a3 print "Powers of [4]=",a4 ︡f98b40ea-bebf-4acc-b39e-97d6b0973aea︡{"stdout": "Powers of [2]= [2, 4, 3, 1]\nPowers of [3]= [3, 4, 2, 1]\nPowers of [4]= [4, 1, 4, 1]"}︡ ︠08a9e211-1dc2-4360-968a-1be305c37062i︠ %htmlInteresting! $[x]^4=[1]$ for all $[x]\not=[0]$ in Z/5Z. Lets look at the powers of $[x]$ in Z/9Z. Recall Z/9Z=$\{[0], [1], [2], [3], [4], [5], [6],[7], [8]\}$.
︡6fae0637-678f-488d-9938-0e2c2bf850b1︡{"html": "Interesting! $[x]^4=[1]$ for all $[x]\\not=[0]$ in Z/5Z. \ufeffLets look at the powers of $[x]$ in Z/9Z. Recall Z/9Z\ufeff=$\\{[0], [1], [2], [3], [4], [5], [6],[7], [8]\\}$.
"}︡ ︠6bc41c1f-c990-4a44-8e97-4f3cca65221d︠ #Powers in Z/9Z a0=[]; a1=[]; a2=[]; a3=[]; a4=[]; a5=[]; a6=[]; a7=[]; a8=[]; for i in range(1,9): a0.append(power_mod(0,i,9)) a1.append(power_mod(1,i,9)) a2.append(power_mod(2,i,9)) a3.append(power_mod(3,i,9)) a4.append(power_mod(4,i,9)) a5.append(power_mod(5,i,9)) a6.append(power_mod(6,i,9)) a7.append(power_mod(7,i,9)) a8.append(power_mod(8,i,9)) print "Powers of [0]=",a0 print "Powers of [1]=",a1 print "Powers of [2]=",a2 print "Powers of [3]=",a3 print "Powers of [4]=",a4 print "Powers of [5]=",a5 print "Powers of [6]=",a6 print "Powers of [7]=",a7 print "Powers of [8]=",a8 ︡b1493250-79e8-4fa1-a0bc-b64f3343d44b︡{"stdout": "Powers of [0]= [0, 0, 0, 0, 0, 0, 0, 0]\nPowers of [1]= [1, 1, 1, 1, 1, 1, 1, 1]\nPowers of [2]= [2, 4, 8, 7, 5, 1, 2, 4]\nPowers of [3]= [3, 0, 0, 0, 0, 0, 0, 0]\nPowers of [4]= [4, 7, 1, 4, 7, 1, 4, 7]\nPowers of [5]= [5, 7, 8, 4, 2, 1, 5, 7]\nPowers of [6]= [6, 0, 0, 0, 0, 0, 0, 0]\nPowers of [7]= [7, 4, 1, 7, 4, 1, 7, 4]\nPowers of [8]= [8, 1, 8, 1, 8, 1, 8, 1]"}︡ ︠4b6cf1ff-4b26-419c-be0d-11944805e73di︠ %htmlHmm, hard to see a pattern yet. Are there any values of $i$ for which $[x]^i=[1]$ for all $[x]\not=[0]$ in Z/9Z? No, but the results for $[x]^6$ are interesting. We see they are all $[1]$ except for $[0]^6, [3]^6,$ and $[6]^6$.
Questions to ponder:
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.
︡4c7b888c-c4b7-48e0-8288-6d5e4b9c413a︡{"html": "Hmm, hard to see a pattern yet. Are there any values of $i$ for which $[x]^i=[1]$ for all $[x]\\not=[0]$ in Z/9Z? No, but the results for $[x]^6$ are interesting. We see they are all $[1]$ except for $[0]^6, [3]^6,$ and $[6]^6$.
\nQuestions to ponder:
\nTask 5: Experiment more below, calculating the powers of the equivalence classes for Z/nZ for at least 2 more value of n.
\nI'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.
"}︡ ︠71e4f133-74aa-4d97-a3b4-a805dbbc1173︠ #Powers in Z/8Z a0=[]; a1=[]; a2=[]; a3=[]; a4=[]; a5=[]; a6=[]; a7=[]; for i in range(1,8): a0.append(power_mod(0,i,8)) a1.append(power_mod(1,i,8)) a2.append(power_mod(2,i,8)) a3.append(power_mod(3,i,8)) a4.append(power_mod(4,i,8)) a5.append(power_mod(5,i,8)) a6.append(power_mod(6,i,8)) a7.append(power_mod(7,i,8)) print "Powers of [0]=",a0 print "Powers of [1]=",a1 print "Powers of [2]=",a2 print "Powers of [3]=",a3 print "Powers of [4]=",a4 print "Powers of [5]=",a5 print "Powers of [6]=",a6 print "Powers of [7]=",a7 ︡213afff2-0acc-43a5-9b28-2b4cf36ccaa8︡{"stdout": "Powers of [0]= [0, 0, 0, 0, 0, 0, 0]\nPowers of [1]= [1, 1, 1, 1, 1, 1, 1]\nPowers of [2]= [2, 4, 0, 0, 0, 0, 0]\nPowers of [3]= [3, 1, 3, 1, 3, 1, 3]\nPowers of [4]= [4, 0, 0, 0, 0, 0, 0]\nPowers of [5]= [5, 1, 5, 1, 5, 1, 5]\nPowers of [6]= [6, 4, 0, 0, 0, 0, 0]\nPowers of [7]= [7, 1, 7, 1, 7, 1, 7]"}︡ ︠d3e453b5-cdb9-4b8d-867c-5599b0d30dbd︠ #Powers in Z/13Z a0=[] a1=[]; a2=[]; a3=[]; a4=[]; a5=[]; a6=[]; a7=[]; a8=[]; a9=[]; a10=[]; a11=[]; a12=[]; for i in range(1,13): a0.append(power_mod(0,i,13)) a1.append(power_mod(1,i,13)) a2.append(power_mod(2,i,13)) a3.append(power_mod(3,i,13)) a4.append(power_mod(4,i,13)) a5.append(power_mod(5,i,13)) a6.append(power_mod(6,i,13)) a7.append(power_mod(7,i,13)) a8.append(power_mod(8,i,13)) a9.append(power_mod(9,i,13)) a10.append(power_mod(10,i,13)) a11.append(power_mod(11,i,13)) a12.append(power_mod(12,i,13)) print "Powers of [0]=",a0 print "Powers of [1]=",a1 print "Powers of [2]=",a2 print "Powers of [3]=",a3 print "Powers of [4]=",a4 print "Powers of [5]=",a5 print "Powers of [6]=",a6 print "Powers of [7]=",a7 print "Powers of [8]=",a8 print "Powers of [9]=",a9 print "Powers of [10]=",a10 print "Powers of [11]=",a11 print "Powers of [12]=",a12 ︡59cc3fc2-6df4-40eb-a0ca-e3f734f9c544︡{"stdout": "Powers of [0]= [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\nPowers of [1]= [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\nPowers of [2]= [2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1]\nPowers of [3]= [3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1]\nPowers of [4]= [4, 3, 12, 9, 10, 1, 4, 3, 12, 9, 10, 1]\nPowers of [5]= [5, 12, 8, 1, 5, 12, 8, 1, 5, 12, 8, 1]\nPowers of [6]= [6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1]\nPowers of [7]= [7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1]\nPowers of [8]= [8, 12, 5, 1, 8, 12, 5, 1, 8, 12, 5, 1]\nPowers of [9]= [9, 3, 1, 9, 3, 1, 9, 3, 1, 9, 3, 1]\nPowers of [10]= [10, 9, 12, 3, 4, 1, 10, 9, 12, 3, 4, 1]\nPowers of [11]= [11, 4, 5, 3, 7, 12, 2, 9, 8, 10, 6, 1]\nPowers of [12]= [12, 1, 12, 1, 12, 1, 12, 1, 12, 1, 12, 1]"}︡ ︠9842cf5e-ee3f-4e17-acf2-a14ceb588bd6︠ #Powers in Z/15Z a0=[] a1=[]; a2=[]; a3=[]; a4=[]; a5=[]; a6=[]; a7=[]; a8=[]; a9=[]; a10=[]; a11=[]; a12=[]; a13=[]; a14=[]; for i in range(1,15): a0.append(power_mod(0,i,15)) a1.append(power_mod(1,i,15)) a2.append(power_mod(2,i,15)) a3.append(power_mod(3,i,15)) a4.append(power_mod(4,i,15)) a5.append(power_mod(5,i,15)) a6.append(power_mod(6,i,15)) a7.append(power_mod(7,i,15)) a8.append(power_mod(8,i,15)) a9.append(power_mod(9,i,15)) a10.append(power_mod(10,i,15)) a11.append(power_mod(11,i,15)) a12.append(power_mod(12,i,15)) a13.append(power_mod(13,i,15)) a14.append(power_mod(14,i,15)) print "Powers of [0]=",a0 print "Powers of [1]=",a1 print "Powers of [2]=",a2 print "Powers of [3]=",a3 print "Powers of [4]=",a4 print "Powers of [5]=",a5 print "Powers of [6]=",a6 print "Powers of [7]=",a7 print "Powers of [8]=",a8 print "Powers of [9]=",a9 print "Powers of [10]=",a10 print "Powers of [11]=",a11 print "Powers of [12]=",a12 print "Powers of [13]=",a13 print "Powers of [14]=",a14 ︡69ed82be-2b59-4bba-a85a-40084b4b5149︡{"stdout": "Powers of [0]= [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\nPowers of [1]= [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\nPowers of [2]= [2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4]\nPowers of [3]= [3, 9, 12, 6, 3, 9, 12, 6, 3, 9, 12, 6, 3, 9]\nPowers of [4]= [4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1]\nPowers of [5]= [5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10]\nPowers of [6]= [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]\nPowers of [7]= [7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1, 7, 4]\nPowers of [8]= [8, 4, 2, 1, 8, 4, 2, 1, 8, 4, 2, 1, 8, 4]\nPowers of [9]= [9, 6, 9, 6, 9, 6, 9, 6, 9, 6, 9, 6, 9, 6]\nPowers of [10]= [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]\nPowers of [11]= [11, 1, 11, 1, 11, 1, 11, 1, 11, 1, 11, 1, 11, 1]\nPowers of [12]= [12, 9, 3, 6, 12, 9, 3, 6, 12, 9, 3, 6, 12, 9]\nPowers of [13]= [13, 4, 7, 1, 13, 4, 7, 1, 13, 4, 7, 1, 13, 4]\nPowers of [14]= [14, 1, 14, 1, 14, 1, 14, 1, 14, 1, 14, 1, 14, 1]"}︡ ︠111bfc65-5a1c-40a5-9498-8e926695c581i︠ %htmlI 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: $a^{c}\equiv 1\pmod{n}$ for all $a^{c} - (a-1)n = 1$ (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
︡0db5f612-6eea-43eb-a0a7-20d07cff9fbd︡{"html": "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
\nThm: $a^{c}\\equiv 1\\pmod{n}$ for all $a^{c} - (a-1)n = 1$ (maybe?)
\nTask 6: Fill in the statement of the above theorem.
\nAppendix 1: Some Useful Sage Functions Related to Modular Equivalence, GCD, Primes, and Factorization
"}︡ ︠51b2f13d-56b2-44eb-be34-e55926d8b542︠ # Greatest Common Divisors gcd(24, 12345) ︡d7f75b9b-7ccb-405b-aa1a-4fa99060ea14︡{"stdout": "3"}︡ ︠44772617-08a7-4f06-9f3b-a1128233e51a︠ # Extended GCD: This finds the GCD and the EA linear combination that produces it. # Example: 2 = (-5)*10 + 1*(52) xgcd(10, 52) ︡81e33438-490a-4c53-9425-79021fe249d3︡{"stdout": "(2, -5, 1)"}︡ ︠10078fb8-f2dc-408d-ae78-9e4141bd6d3f︠ # Multiplicative inverses # To find the inverse of 3 mod 100: # Note: we know 3 * 33 = 99 = -1 mod 100 # so 3 *(-33) = -99 = 1 mod 100 inverse_mod(3, 100) ︡36e6dce5-efac-4988-b251-51269ed8f4e6︡{"stdout": "67"}︡ ︠71749e68-ff83-42fb-9684-1da0a9edf0f4︠ # What if we try to find the inverse of 2 modulo 100? inverse_mod(2, 100) ︡474e1963-d3b7-40a7-bf68-b82f12e74496︡{"stderr": "Traceback (most recent call last):\n File \"