301 Abstract Algebra
2:00 - 2:50 MWF
Hentzel 432 Carver
hentzel@iastate.edu
Web Page   http://www.math.iastate.edu/hentzel/class.301

Text: A First Course in Abstract Algebra, sixth Edition
by John B. Fraleigh
Course: Chapter 1,2,3,4,5

Wednesday, September 26, 2001  Professor Tondra is looking
for a math student to be a representative in the LAS
assembly.  See me or Tondra for details.

Main idea: Is there a better fraction for Pi than 22/7? 
Key Words: Rational approximation, 
Goal: Learn to create the best rational approximations
   to decimal numbers.       
                                            n 
Theorem: In any finite group G of order n, g   = e.

                                2   3         r 
Proof:  Given g in G, <g> = {g,g  ,g  , ..., g  } where

 r
g   = e and g is of order r.  Since <g> is a subgroup

                                                n
|<g>| divides n.  So n = rs for some s.  Then  g   = 

 rs        r s    s
g      = (g )  = e  = e. 


(a)  What are the possible orders for elements of S4?
ans:  1,2,3,4,6,8,12,24  but only 1,2,3,4 actually occur.
(b) What are the possible orders for elements of Z24?
ans: Same list and they all occur.  List the elements of
each order

In[2]:= Do[Print[i," ",GCD[i,24]," ",24/GCD[i,24]],{i,1,24}]
 i GCD order
 1  1   24
 2  2   12
 3  3    8
 4  4    6
 5  1   24
 6  6    4
 7  1   24
 8  8    3
 9  3    8
10  2   12
11  1   24
12 12    2
13  1   24
14  2   12
15  3    8
16  8    3
17  1   24
18  6    4
19  1   24
20  4    6
21  3    8
22  2   12
23  1   24
24 24    1




Theorem:  The set of elements of Zn relative prime to n
form a group under multiplication.

Zn# = {i in Zn | GCD(i,n) = 1}.
Proof: We show that Zn# is a group.  We will Show that Zn#:  
(a) is associative, (b) has an identity, and (c) has inverses 

(a) I could say that the associativity of Zn# follows from the
associativity of multiplication for the integers.  It does, but
it is not that obvious.  The problem occurs because we have not
really defined what Zn is. Once we do that, (which will be much
later on this semester), then the associativity will be obvious.

(b) 1 is certainly relatively prime to n and 1 is the multiplicative
identity.

(c)  Given a in Zn#, since GCD(a,n) = 1, there exists integers
x and y such that ax+ny = 1.  In Zn this says that
ax == 1 mod n so x is the multiplicative inverse of a.  x has to
be relatively prime to n since from the equation ax+ny = 1, any 
divisor of x and n must divide 1.  

If Zn where n is a product of two primes, then n=pq and

|Zn#| = (p-1)(q-1).

Proof:   If GCD[i,n] =/= 1 then GCD[i,n] = p or q or pq.
The numbers i where GCD[i,n] = p are p,2p,3p,...,pq.
The numbers i where GCD[i,n] = q are q,2q,3q,...,pq.
All together, the remainder are pq-p-q+1 = (p-1)(q-1)

Previous problems;

2.  Given n = 11663 and r = 7 encode the message:

        I       A  M      S  I  C  K   
        9       1 13     19  9  3 11

 9 -> Mod[ 9^7, 11663] = 1139 
 1 -> Mod[ 1^7, 11663] =    1
13 -> Mod[13^7, 11663] = 1577 
19 -> Mod[19^7, 11663] = 7756 
 9 -> Mod[ 9^7, 11663] = 1139
 3 -> Mod[ 3^7, 11663] = 2187 
11 -> Mod[11^7, 11663] = 9961

3.  Break the code and decipher the message.

        7133 8088   9475 8088 1577 8147

The whole security of the RSA code is that factoring
is difficult.  If we can factor 11663 the code is
broken.  11663 = 107*109.

We have to find the inverse of r = 7 mod (p-1)(q-1) = 11448
We know 7 has an inverse mod 11448 because GCD(7,11448) = 1.
We find the inverse using the Euclidean Algorithm.













   1635 
7 11448 
  11445
  -----  2 
      3  7
         6 
        ---  3
         1   3
             3
            ---
             0

1635    2     3
   1  1635  3271 11448
   0    1     2    7

  3271 7 - 2 11448 = 1

And     3271*7  =  22897 = 1 mod 11448 

The private key to crack the code is 3271.
f[x_] := Mod[x^3271,11663]
Just to check we try the encryption of I AM SICK 
f[{1139,1,1577,7756,1139,2187,9961}] = 

{9, 1, 13, 19, 9, 3, 11}
 I  A   M   S  I  C   K

So it seems to work
To break the code

f[{7133,8088,  9475,8088,1577,8147}] = 

{7, 15,    8, 15, 13, 5}
 G   O     H   O   M  E

1.  Find the smallest distance that can be measured with a
(unmarked) meter stick and an (unmarked) yard stick.  
1 meter = 39.37 inches.

             1
     3600 3937
          3600   10
           337 3600
               3370   1
                230 337
                    230   2
                    107 230
                        214   6
                         16 107
                             96  1
                             11 16
                                11  2
                                 5 11
                                   10 5
                                    1 5
                                      5
                                      0

   1    10     1    2    6      1    2    5
   1     1    11   12   35    222  257  736  3937
   0     1    10   11   32    203  235  673  3600

So  -736 36.00 + 673 39.37 = 0.01

So lay out 673 of the meter sticks and come back with 736 or the
yard sticks and the difference will be 0.01 inches.



Assignment:

1.  Pi = 3.141592654  approximately.  Find the best rational
approximations to Pi using numerators and denominators no larger
than 1000.

2.  There are three kinds of years.
Calendar Year is   365 days or 366 days during leap year.
Tropical year is   365 days, 5 hours, 48 minutes, 46 seconds
                   =========================================
It is the time spend by the sun in its apparent passage from vernal
equinox to vernal equinox.
Sidereal year 365 days, 6 hours,  9 minutes, 9 seconds
             ========================================
It is the time spent by the sun making is apparent passage from 
a fixed star and back to the same position again.


The difference in time from the Tropical year to the sidereal year 
is due the the precession of the equinoxes.


Use the Tropical year against the day to get the best approximating 
fractions.  

Tropical year is   ((365*24 + 5)*60 + 48 )*60 + 46  seconds long.
One day is 24*60*60 seconds long.


(a)  Best approximate  Tropical year/day.  Here is the start of the 
magic tableau. Finish filling it out.


365,   4,    7,     1,     3,     5,      ?,        ?, 
  1, 365, 1461, 10592, 12053, 46751,      ?,        ?  <--- days 
  0,   1,    4,    29,    33,   128,      ?,        ?  <--- years

(b)  The numbers in the 6 th column are 46751 and 128.  This
says that in 128 years there are 46751 days.  If we compute
46751-365*128 = 31.  This means that in a period of 128 years
we have to insert 31 days.  How many days have to be
inserted for the other columns?  


(c)  The Gregorian calendar rule is this.
     Put in a February 29 if the year is divisible by 4
     unless it is a century.  Centuries are leap years if
     they are divisible by 400.

     In 128 years the number of extra days added by this rule
     is   Floor[128/4] - Floor[128/100] + Floor[128/400]
      =       32  - 1 + 0  
      = 31.  Thus the Gregorian rule works for 128 years.

     Find how many of the extra days are accounted for by
the Gregorian rules?

(d)  Approximately how often to we have to add an additional

day in addition to the Gregorian rules?