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.