[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. Generators and relations

Below are some presentations of groups given by generators and relations. For each group, compute the number of elements, and prove that your count is correct.

  1. G1 = (a | a17=e). Solution: |G1| = 17. Proof: Any element of G1 must be of the form ax where x is an integer; but if x = y mod 17 then ax = ay. So we are left with just a0, a1, ..., a16 and G1 is isomorphic to Z17.

  2. G2 = (a,b | a3=e, ab-1=a-1). Solution: Here the first step is to get rid of b. We have ab-1=a-1; multiply both sides on the right by b to get a = a-1b and then on the left by a to get b = a2. Since b doesn't add any new elements, we are left with G2 = (a | a3 = e) which is isomorphic to Z3 by the same argument as in part 1. So |G2| = 3.

  3. G3 = (a,b,c | a2=b2=c2=e, ab=c, bc=a, ca=b). Solution: |G3| = 4; the elements are e, a, b, and c. There are no separate inverse elements since each element is its own inverse, and any product of two or more generators can be reduced to a single generator or the identity by replacing any x-1 by x and applying the relations to reduce pairs of generators to singletons.

2. A homomorphic problem

Let G be a group with |G| = 2n and let f be a surjective homomorphism from G to H. Prove that if |H| > 1, then |H| is even. Note new assumption that |H| > 1 added 2004-11-30.

Solution: Use the First Isomorphism Theorem (see AlgebraicStructures) to show that H is isomorphic to the quotient group G/ker(f). Then observe that each element of G/ker(f) is a coset of a subgroup of G, so that all of them have the same size |G| = |H|*|G/ker(f)|. It follows that |H| divides |G|, which implies that |H| is a power of 2. Since |H| = 2k > 1, |H| must be even.

3. Triskaidekainversia

Compute x-1 for each x in Z*13. Solution: starting with 1-1: 1, 7, 9, 10, 8, 11, 2, 5, 3, 4, 6, 12.

4. A little problem

Show that if p is prime and (p-1)/2 is odd, there is no number n such that p divides (n2+1). Hint: consider n2 mod p and apply Fermat's Little Theorem.

Solution: Suppose there is such an n. Then n2 + 1 = 0 (mod p) and n2 = -1 (mod p). But then (n2)((p-1)/2) = np-1 = (-1)((p-1)/2) = -1 (mod p) (we are using here the fact that (p-1)/2 is odd in the last step). This contradicts Fermat's Little Theorem, which says that np-1 = 1 (mod p).

2014-06-17 11:57