# 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^{2} = 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)^{2} = (c^{2},d^{2}) 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

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*^{1} 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^{2}h^{3}g^{27}hghgh^{2}g, etc.). Prove that S_{n} is bicyclic for any n > 0.

## 4.1. Solution

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

When n=2, S_{1} 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.

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