3145.sagews

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 $\phi$, 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 $\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.

# euler_phi(n) returns the number of integers (less than n and greater than zero) which are relatively prime to n.
euler_phi(5)

4

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 $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). 

(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))

(2, 4, 8, 6, 18, 54, 20, 100, 500)

# calculating euler_phi(p^i)

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.

(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))

(36, 60, 24, 78, 32, 44, 24, 70, 24, 72, 36, 40)

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}}$

 

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.

# Modular Arithmetic
# gives 100 mod 34
Mod(100, 34)

32

# a^n mod m
# 2^100 mod 10 = 6
power_mod(2, 100, 10)

6

Now 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.

# 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

Powers of [2]= [2, 4, 3, 1] Powers of [3]= [3, 4, 2, 1] Powers of [4]= [4, 1, 4, 1]

Interesting!  $[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]\}$.

#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

Powers of [0]= [0, 0, 0, 0, 0, 0, 0, 0] Powers of [1]= [1, 1, 1, 1, 1, 1, 1, 1] Powers of [2]= [2, 4, 8, 7, 5, 1, 2, 4] Powers of [3]= [3, 0, 0, 0, 0, 0, 0, 0] Powers of [4]= [4, 7, 1, 4, 7, 1, 4, 7] Powers of [5]= [5, 7, 8, 4, 2, 1, 5, 7] Powers of [6]= [6, 0, 0, 0, 0, 0, 0, 0] Powers of [7]= [7, 4, 1, 7, 4, 1, 7, 4] Powers of [8]= [8, 1, 8, 1, 8, 1, 8, 1]

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$. 

Questions to ponder: 

1. What is a signifficant difference between $5$ and $9$? (5 is prime, 9 is not)
2. Is there a difference between the sets of numbers $\{0, 3, 6\}$ and $\{1, 2, 4, 5, 7, 8\}$ in relation to the number 9?  Similarly, is there a way in which $\{1,2, 3,4\}$ are related to $5$ in the same manner that $\{1,2, 4, 5,7,8\}$ 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)
3. Can you find a relationship that relates $4$ to $5$ in the same way that $6$ is related to $9$? 

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.

#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

Powers of [0]= [0, 0, 0, 0, 0, 0, 0] Powers of [1]= [1, 1, 1, 1, 1, 1, 1] Powers of [2]= [2, 4, 0, 0, 0, 0, 0] Powers of [3]= [3, 1, 3, 1, 3, 1, 3] Powers of [4]= [4, 0, 0, 0, 0, 0, 0] Powers of [5]= [5, 1, 5, 1, 5, 1, 5] Powers of [6]= [6, 4, 0, 0, 0, 0, 0] Powers of [7]= [7, 1, 7, 1, 7, 1, 7]

#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

Powers of [0]= [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Powers of [1]= [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Powers of [2]= [2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1] Powers of [3]= [3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1] Powers of [4]= [4, 3, 12, 9, 10, 1, 4, 3, 12, 9, 10, 1] Powers of [5]= [5, 12, 8, 1, 5, 12, 8, 1, 5, 12, 8, 1] Powers of [6]= [6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1] Powers of [7]= [7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1] Powers of [8]= [8, 12, 5, 1, 8, 12, 5, 1, 8, 12, 5, 1] Powers of [9]= [9, 3, 1, 9, 3, 1, 9, 3, 1, 9, 3, 1] Powers of [10]= [10, 9, 12, 3, 4, 1, 10, 9, 12, 3, 4, 1] Powers of [11]= [11, 4, 5, 3, 7, 12, 2, 9, 8, 10, 6, 1] Powers of [12]= [12, 1, 12, 1, 12, 1, 12, 1, 12, 1, 12, 1]

#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

Powers of [0]= [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Powers of [1]= [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Powers of [2]= [2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4] Powers of [3]= [3, 9, 12, 6, 3, 9, 12, 6, 3, 9, 12, 6, 3, 9] Powers of [4]= [4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1] Powers of [5]= [5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10, 5, 10] Powers of [6]= [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6] Powers of [7]= [7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1, 7, 4] Powers of [8]= [8, 4, 2, 1, 8, 4, 2, 1, 8, 4, 2, 1, 8, 4] Powers of [9]= [9, 6, 9, 6, 9, 6, 9, 6, 9, 6, 9, 6, 9, 6] Powers of [10]= [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10] Powers of [11]= [11, 1, 11, 1, 11, 1, 11, 1, 11, 1, 11, 1, 11, 1] Powers of [12]= [12, 9, 3, 6, 12, 9, 3, 6, 12, 9, 3, 6, 12, 9] Powers of [13]= [13, 4, 7, 1, 13, 4, 7, 1, 13, 4, 7, 1, 13, 4] Powers of [14]= [14, 1, 14, 1, 14, 1, 14, 1, 14, 1, 14, 1, 14, 1]

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: $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

# Greatest Common Divisors
gcd(24, 12345)

3

# Extended GCD:  This finds the GCD and the EA linear combination that produces it.
# Example: 2 = (-5)*10 + 1*(52)
xgcd(10, 52)

(2, -5, 1)

# 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)

67

# What if we try to find the inverse of 2 modulo 100?
inverse_mod(2, 100)

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_8.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("IyBXaGF0IGlmIHdlIHRyeSB0byBmaW5kIHRoZSBpbnZlcnNlIG9mIDIgbW9kdWxvIDEwMD8KaW52ZXJzZV9tb2QoMiwgMTAwKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmpbSnUXy/___code___.py", line 3, in <module> exec compile(u'inverse_mod(_sage_const_2 , _sage_const_100 )' + '\n', '', 'single') File "", line 1, in <module> File "/usr/local/sage2/local/lib/python2.6/site-packages/sage/rings/arith.py", line 1740, in inverse_mod return a.inverse_mod(m) File "integer.pyx", line 5155, in sage.rings.integer.Integer.inverse_mod (sage/rings/integer.c:28828) ZeroDivisionError: Inverse does not exist.

# Factoring is useful (and hard!)
factor(1234567)

127 * 9721

# Primality Testing
is_prime(987654321)

False

#Sometimes we want to find a big prime:
next_prime(2^40)

1099511627791

# Or the nth prime
nth_prime(10)

541