cs 280 hw2

1.  Do question 8 from hw1.

2.  Prove that   (1+a)^p = (1 + a^p) mod p   if p is prime and a is an integer, 0 <= a < p.   
   Is it still true if p is not prime?

3.  How many different binary operations (recall the formal definition of a function) are there 
   on a set A having n elements?  List all of them for the set A = {a,b} and indicate how many 
   of them

   (i)   are commutative,
   (ii)  are associative,
   (iii) have identity elements,
   (iv)  have zero divisors.

4.  Let G be a group (written multiplicatively) and A a non-empty set.  We say that G "acts on" A 
  if there is a function  f : G x A --> A  (where we write  f(g,a) := g.a) satisfying

   (a)  g.(h.a) = (gh).a  for all g and h in G and for all a in A,  and
   (b)  1.a = a  for all a in A.

  Prove that

   (i)   given g in G, the function p_g : A --> A given by  p_g(a) := g.a  is a bijection,
   (ii)  the relation on A given by a ~ b iff there exists a g in G with  b = g.a  is an 
         equivalence relation,
   (iii) if G_a := { g in G | g.a = a }  then  |[a]| = |G|/|G_a|, where [a] is the equivalence 
         class of a under the relation in part (ii).

5.  Let X be the set  X := {1,2,3,...,n}  and let S(X) be the set of all permutations of X 
  (i.e., bijections from X to X).  Notice that we could write any given permutation by listing 
  where individual elements of X go, for example as:

                  ( 1 2 3 4 5 6 7 8 9 )
                  ( 1 4 6 2 8 9 7 5 3 )

  where we mean that the element in row 1 is mapped to the corresponding element beneath it in 
  row 2 by the given permutation, so 1 goes to 1, 2 goes to 4, 3 goes to 6, etc..  Adopting a 
  shorthand notation, we could write this more succinctly as:

                  (1) (2 4) (3 6 9) (5 8)

  meaning that 1 goes to 1, 2 goes to 4 which goes to 2, 3 goes to 6 which goes to 9 which goes to 3, 
  and 5 goes to 8 which goes to 5 (we call such things "cycles" for the obvious reason).  Thinking 
  of the order we write composition of functions, we could write a succession of permutations (to be 
  read from right to left), for example:

                  (1 2 4) (3 5 7 9) (1 3 9) (2 3 4 5 6 8)

  which could, with a little work, be seen to be the same as (1 5 6 8 4 7 9 2 3).  Show 

  (i)   that every permutation of X can be written as a composition of disjoint cycles,
  (ii)  that every permutation can be written as a composition of transpositions (cycles of 2 elements),
  (iii) that if p in S(X) can be written using an even number of transpositions, then it cannot be 
        written using an odd number of transpositions, and vice versa.