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.