## Math 417 Homework 5 Solutions

The math symbols on this page seem to view best if your browser is IE.

• [1] Problem #24 on p. 24. (Hint: see Example 10 on p. 16.)

First note that a \$47 bet cannot be placed. If it could, then there is a solution to 7x + 9y = 47, where x and y are integers and both at least 0. Thus 7x <= 47 so x < 7 (hence 0 <= x <= 6), and 9x <= 47 so 0 <= x <= 5. For each y from 0 to 5 we check that 47 - 9y is not a multiple of 7: 47 - 9(0) = 47, 47 - 9(1) = 38, 47 - 9(2) = 29, 47 - 9(3) = 20, 47 - 9(4) = 11, 47 - 9(5) = 2. Thus there is no appropriate solution to 7x + 9y = 47, hence a \$47 bet cannot be placed.

Now we show by induction that any bet of \$48 or more CAN be placed. Let S be the set of all positive integers n such that there is a solution to n = 7x + 9y, where x and y are nonnegative integers. We want to show that n is in S for every integer n >= 48. Since (x, y) = (3, 3) is a solution to 7x + 9y = 48, 48 is in S. Now assume that N is in S for some N >= 48; we will show that then N+1 is in S. It then follows by induction (using Theorem 0.4) that N is in S for every n >= 48. But the fact that N is in S means that we have a solution (a, b) to 7x + 9y = N. Since N >= 48 and a >= 0 and b >= 0, it cannot be true that both a < 5 and b < 3 (since then we would have 7a + 9b <= 7(4) + 9(2) = 46, which is less than 48). Hence either a >= 5 or b >= 3. If a >= 5, then using 7(-5) + 9(4) = 1 we have 7(a - 5) + 9(b + 4) = N + 1. Thus x = a - 5 and y = b + 4 gives a solution in nonnegative integers to 7x + 9y = N + 1, which N+1 is in S if a >= 5. If instead all we know is that b >= 3, then we use 7(4) + 9(-3) = 1 to get 7(a + 4) + 9(b - 3) = N + 1, and again we see that N+1 is in S. Hence in all cases N+1 is in S, so n is in S whenever N >= 48.

Finally, here's how to do the problem using the other form of induction, Theorem 0.5. We already know that a bet of \$47 can't be placed. Let S be the set of all positive integers n such that there is a solution to n = 7x + 9y, where x and y are nonnegative integers. Note that 48 through 54 are in S: 48 = 3(7) + 3(9), 49 = 7(7) + 0(9), 50 = 2(7) + 4(9), 51 = 6(7) + 1(9), 52 = 1(7) + 5(9), 53 = 5(7) + 2(9), 54 = 0(7) + 6(9). Now assume that for some integer k > 54, the integers from 48 to k-1 are all in S. Thus k-7 > 54 - 7 = 47 is in S, hence there is a solution (a, b) with x = a and y = b being nonnegative integers such that 7x + 9y = k-7. Thus (a+1, b) is a solution to 7x + 9y = k, so k is in S. This proves that every integer n >= 48 is in S, as we wished to show.

• [2] Let {f1, f2, f3, ...} be a sequence of integers such that f1 > 1 and for n > 1 such that fn > 3fn - 1 + 2. Use induction to prove that fn > 3n/2 - 1 for every integer n > 0. (Indicate which form of induction you used; Theorem 0.4 or 0.5.)

Since we are given that f1 > 1, we know f1 > 31/2 - 1. Now assume that fn > 3n/2 - 1 for some n >= 1; we want to show that fn+1 > 3n+1/2 - 1. Our result then follows by induction from Theorem 0.4. But we are given that fn+1 > 3fn + 2, hence, substituting in for fn we see that fn+1 > 3fn + 2 > 3(3n/2 - 1) + 2 = 3n+1/2 - 1, as we wanted to show.

• [3] Let {f0, f1, f2, f3, ...} be a sequence of integers such that 1 < f0 < f1 and for n > 1 such that fn + 1 > fn + fn - 1. Use induction to prove that fn > 1.6n for every integer n > -1. (Indicate which form of induction you used; Theorem 0.4 or 0.5.)

From what we are given, we see that f0 > 1 = 1.60 and f1 > 1. But f1 is an integer, so f1 >= 2 > 1.61. Now assume that n > 1 and that fk > 1.6k for 0 <= k <= n. We want to show that fn+1 > 1.6n+1; then our result will follow by induction, using Theorem 0.5. But we are given that fn+1 > fn + fn - 1, so fn+1 > fn + fn - 1 > 1.6n + 1.6n-1 = (1.6 + 1)(1.6n-1) > (1.62)(1.6n-1) = 1.6n+1, as we wanted to show.

• [4] Problem 40 on p. 84. [Note: Ç should be an intersection symbol, and the symbols < and > should be the symbols showing that <g> is the cyclic group generated by g.]

I claim that <m> Ç <n> is <lcm(m, n)>. Certainly lcm(m, n) is in both <m> and <n>, hence in the intersection. Now by Problem 2 on Homework 4, this means <lcm(m, n)> is a subgroup of <m> Ç <n>. To verify the reverse inclusion (and hence establish the equality <m> Ç <n> = <lcm(m, n)>), let x be an element of the intersection. Thus x is in <m>, so x is a multiple of m, and x is in <n>, so x is a multiple of n. But this means that x is a common multiple of m and n, and hence (see below) x is a multiple of lcm(m, n), so x is in <lcm(m, n)>, as we wanted to show.

[Here I show that any common multiple of m and n is a multiple of c = lcm(m, n). Let x be a common multiple of m and n. Write x = cq + r, where 0 <= r < c. Then since r = x - cq, we see that r is also a common multiple of m and n, but it is less than the least common multiple, c. Thus r can't be positive, since the least common multiple is the least positive integer which is a common multiple. Thus r = 0, so x = cq is a multiple of c.]

• [5] Problem 54 on p. 85.

[Implicitly, we are assuming here that |a| and |b| are finite.] Say x is an element of <a> Ç <b>. Then x is in <a>, so <x> is a subgroup of the cyclic group <a>, so |x| = |<x>| divides |<a>| = |a|. But likewise |x| divides |b|, so |x| divides the gcd(|a|, |b|). But gcd(|a|, |b|) = 1 since |a| and |b| are relatively prime, so |x| = 1. Thus x = e. I.e., the only thing in the intersection is e, so the intersection equals {e}, as we wanted to show.

• [6] Problem 4 on p. 111.

(a) The cycle decomposition for the given permutation is (1 2)(3 5 6)(4), or just (1 2)(3 5 6) if we suppress 1-cycles. The least common multiple of the lengths of the cycles is thus lcm(2, 3) = 6. Thus |(1 2)(3 5 6)| = 6.

(b) The cycle decomposition for the given permutation is (1 7 5 3)(2 6 4), so the least common multiple of the lengths of the cycles is lcm(4, 3) = 12. Thus |(1 7 5 3)(2 6 4)| = 12.

• [7] Problem 8 on p. 111.

Every element x of A10 can be written as a product of disjoint cycles, and |x| is the least common multiple of the lengths of those cycles. Moreover, x must be an even permutation. But given any positive integers whose sum is 10, we can easily write down disjoint cycles whose lengths are the positive integers and check to see if the permutation is even (all we need is that there are an even number of cycles of even length). Thus the maximum order among elements in A10 is just the maximum least common multiple among sets of positive integers whose sum is 10 and which correspond to an even permutation. So consider a sum of positive integers whose total is 10. Let s be the largest summand in our sum.
• If L = 10, there is only one summand and the lcm is 10. But a 10-cycle is odd so although this case occurs in S10, it does not occur in A10.
• If L = 9, there are only two summands, 9 and 1, and the lcm is 9.
• If L = 8, there are only two cases, 8 + 2 = 10 and 8 + 1 + 1 = 10 (but this second case would correspond to an odd permutation), so the lcm is 8.
• If L = 7, there are only 3 cases, 7 + 3 = 10, 7 + 2 + 1 = 10 and 7 + 1 + 1 + 1 = 10, so the lcm is at most 21 and since a product of a 7-cycle times a 3-cycle is even, A10 really does have an element of order 21.
• If L = 6, the cases are either 6 + 4 = 10, 6 + 3 + 1 = 10 or the summands other than 6 are all 2's or 1's. Thus the lcm is at most 12.
• If L = 5, the cases are either 5 + 5 = 10, 5 + 4 + 1 = 10, 5 + 3 + 2 = 10, 5 + 3 + 1 + 1 = 10, or the summands other than 5 are all 2's or 1's. Since the cases 5 + 4 + 1 = 10 and 5 + 3 + 2 = 10 correspond to odd permutations, the lcm here is at most 15 = lcm(5, 3).
• If L <= 4, every summand is either 1, 2, 3 or 4, and lcm(2, 3, 4) = 12.
Thus the largest order of an element of A10 is 21; here is an even permutation of order 21: (1 2 3 4 5 6 7)(8 9 10). (In S10, the same analysis leads to the greatest order being 30, such as the permutation (1 2 3 4 5)(6 7 8)(9 10) has.)