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 x² = 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 = p^k 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)² = (c²,d²) in ℤ^*_a×ℤ^*_b. Note that because gcd(x,m) = 1, c and d are both nonzero. Then y is also equal to (-c,d)², (c,-d)², and (-c,-d)². 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

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

3.1. Solution

If a = 1 (mod p), then

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 a^p-1 = 1 (mod p) to compute:

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.

4.1. Solution

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

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

For larger n, recall that any permutation in S_n 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.