[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. 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.

1.1. Solution

We need to check that (ℚ,*) satisfies closure, associativity, and has an identity but does not have an inverse for at least one a∈ℚ. As always, closure is trivial. For associativity, compute a*(b*c) = a(b*c) + a + (b*c) = abc + ab + ac + a + bc + b + c and (a*b)*c = (ab+a+b)*c = abc + ac + bc + ab + a + b + c = abc + ab + ac + a + bc + b + c after rearranging the terms.The identity is 0: 0*a = 0a + 0 + a = a (and similarly a*0 = a0 + a + 0 = a). So we have a monoid.

To show that it is not a group, we need to find some a such that for all b, a*b ≠ 0 (since 0 is the identity). Let's try to do it by first looking for the inverse of some arbitrary a. We need 0 = a*b = ab + a + b. Solving for b gives b = a/(a+1), which blows up when a = -1. So we expect that -1 does not have an inverse, which we can verify by computing (-1)*b = (-1)b + -1 + b = -1 ≠ 0 for any b.

2. Square roots

An element x of ℤ*m is called a square root of y mod m if x2 = y (mod m). Prove that if m is odd and has at least two distinct prime factors, then any y in ℤ*m either has no square roots mod m or at least four square roots mod m.

2.1. Solution

Let m = ab where gcd(a,b) = 1 and both a and b are greater than 1; such a and b exist, since m has at least two distinct prime factors p and q and we can take a = pk for some maximal k. By the Chinese Remainder Theorem, we can factor ℤ*m as ℤ*a×*b. Suppose that y∈ℤ*m has a square root x. Split x as (c,d) so that y = (c,d)2 = (c2,d2) in ℤ*a×ℤ*b. Note that because gcd(x,m) = 1, c and d are both nonzero. Then y is also equal to (-c,d)2, (c,-d)2, and (-c,-d)2. These square roots are distinct precisely when c ≠ -c (mod a) and d ≠ -d (mod b). But if c = -c (mod a) we have 2c = 0 (mod a), which can only occur c = 0 or gcd(2, a) ≠ 1. If c = 0, we have y = 0 (mod a) which implies a|gcd(a,m) and y is not in ℤ*m. Alternatively if 2c = 0 (mod a), then gcd(2,a) ≠ 0 and a is even, contrary to the assumption that m = ab is odd. A similar argument shows d ≠ -d (mod b), and the four square roots are distinct.

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).

3.1. Solution

If a = 1 (mod p), then

\sum_{n=1}^{p-1} a^n = \sum_{n=1}^{p-1} 1 = p-1 \pmod{p}.

If p|a, then each term in the sum is congruent to 0 mod p, so the sum is as well.

Otherwise, use (a) the geometric series formula, (b) the fact that gcd(a-1, p) = 1 implies that (a-1)-1 exists mod p, and (c) Fermat's Little Theorem ap-1 = 1 (mod p) to compute:

\sum_{n=1}^{p-1} a^n
&=& \frac{a^{p} - 1}{a - 1} - 1 
&=& (a-1)^{-1} (a\cdot a^{p-1} - 1) - 1
(a-1)^{-1} (a - 1) - 1 = 1-1 = 0 \pmod{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 bicyclic1 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, g2h3g27hghgh2g, etc.). Prove that Sn is bicyclic for any n > 0.

4.1. Solution

When n=1, S1 is the trivial group consisting only of the identity permutation e; let g = h = e.

When n=2, S1 contains only e and the permutation (1 2); let g = h = (1 2).

For larger n, recall that any permutation in Sn can be written as the product of transpositions. We will reduce this further to adjacent transpositions (of the form (k k+1)) and show how all adjacent transpositions can be built from a single fixed transposition (1 2) and a rotation (1 2 3 ... n).

First consider some transposition (i j) with i < j. We can construct (i j) from adjacent transpositions by moving i up to j, swapping them, and then moving j back down to i's old position: (i j) = ∏k=j-2 downto i (k k+1) ∏k = i to j-1 (k k+1). This still leaves us with n-1 adjacent transpositions.

To knock this set the rest of the way down, observe that (k k+1) = (1 2 3 ... n)k-1(1 2)(1 2 3 ... n)n-k+1, since the first applied set of n-k+1 rotations shifts k and k+1 to positions 1 and 2, the (1 2) transposition swaps them, and then the last applied set of k-1 rotations puts everything else back. So (1 2) and (1 2 3 ... n) between them generate all adjacent transpositions, and thus all transpositions and finally all permutations.

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

2014-06-17 11:57