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.

Here are the /Solutions.

1. An unusual binary operation

For any two rational numbers a and b, define a*b = ab + a + b. Show that the rationals with this operation are a monoid but not a group.

2. Square roots

An element x of ℤ^*_m is called a square root of y mod m if x² = y (mod m). Prove that if m is odd and has at least two distinct prime factors (was: m is composite, which is not enough), then any y in ℤ^*_m either has no square roots mod m or at least four square roots mod m.

3. A big sum

Let p be prime and let a be any integer. Prove that

$\sum_{n=1}^{p-1} a^n$

is a multiple of p if and only if a ≠ 1 (mod p).

4. Bicyclic groups

Recall that a group is cyclic if every element can be written as the product of zero or more copies of some single generator g. Call a group bicyclic¹ if every element can be written as the product of some sequence of zero or more copies of two generators g and h (e.g., <>, g, h, gh, hg, g²h³g²⁷hghgh²g, etc.). Prove that S_n is bicyclic for any n > 0.

Not a real mathematical term in this context. (1)