quiz.sagews

#Group theory worksheet:
#Studied with MIDN Miller


#Choose two primes p and q
#p = 13, q = 7, n = p*q
n = 91
phi = 72
count = 0
b = []
f = []
for a in range(1,n):
    if gcd(a,n) == 1:
        b.append(a)
        #calculate phi(n) = number of invertible elements
        count += 1
    else:
        f.append(a)
    #end
print str(b)
print str(f)

#factor non invertible elements
for p in range(0,17):
    factor(f[p])
    #end
#Observation:  All the factorizations involve 13 and 7, which are my chosen p and q

#Print phi(n)
print  "phi(n) =" + str(count)

o = []
#phi = 72
for c in range(0, 73):
    for m in range(1, n):
        if power_mod(b[c], m, n) == 1:
            o.append(m)
            break
            #end
print o

#verify order of element g divides phi(n)
for i in range(0, 73):
    if phi%o[i] != 0:
        print "Does not divide"
        #end

#Question 3:
#lists for each cyclic subgroup
g1 = []
g2 = []
g3 = []

g = [b[4], b[8], b[12]]
m = [o[4], o[8], b[12]]

for i in range (1, m[0]):
    g1.append(power_mod(g[0], i, n))

for i in range(1, m[1]):
    g2.append(power_mod(g[1]), i, n))

for i in range(1, m[2]):
    g3.append(power_mod(g[2]), i, n))

print g1
print g2
print g3

factor m

[1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27, 29, 30, 31, 32, 33, 34, 36, 37, 38, 40, 41, 43, 44, 45, 46, 47, 48, 50, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 64, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90] [7, 13, 14, 21, 26, 28, 35, 39, 42, 49, 52, 56, 63, 65, 70, 77, 78, 84] 7 13 2 * 7 3 * 7 2 * 13 2^2 * 7 5 * 7 3 * 13 2 * 3 * 7 7^2 2^2 * 13 2^3 * 7 3^2 * 7 5 * 13 2 * 5 * 7 7 * 11 2 * 3 * 13 phi(n) =72 [1, 12, 6, 6, 12, 12, 4, 3, 6, 12, 6, 12, 3, 6, 12, 12, 12, 3, 6, 12, 6, 2, 3, 6, 12, 12, 12, 4, 6, 12, 6, 6, 12, 6, 12, 12, 12, 12, 6, 12, 6, 3, 12, 6, 4, 12, 12, 12, 6, 6, 2, 6, 12, 6, 6, 12, 12, 12, 3, 6, 12, 3, 12, 3, 6, 4, 12, 12, 6, 6, 12, 2]