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.
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.
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
is a multiple of p if and only if a ≠ 1 (mod p).
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 ap-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 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.
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.
Not a real mathematical term in this context. (1)