Homework

Attempt all parts of a homework. Each question carries 5 marks, unless stated otherwise. The chapter and exercise numbers refer to the text: An Introduction to Mathematical Thinking: Algebra and Number Systems, by Gilbert and Vanstone. The solutions provided represent only one of several different correct ways of solving the exercises.

• HW 1    (out May 2,   due May 10):    Chapter 1, Page 20--22.
1. Exercise 11
2. Exercise 25. Please argue in English whether the statements are equivalent or not. Truth tables will not be considered as satisfactory answers.
3. Exercises 33, 35
4. Exercises 47, 48. For each, give an example of a universe so that the expression has the opposite truth value.
5. Exercise 51

• HW 2    (out May 9,   due May 17):
1. Chapter 1, Exercise 41, 43. Simplify so that no compound statement is negated in your final expression.
2. Chapter 1, Exercise 64.
3. Chapter 4, Exercise 28.
4. Show that one can make up any amount of postage greater than 7 using only 3-cent and 5-cent stamps. In other words, for every n greater than 7, there are non-negative integers k and l such that n = 3k+ 5l.
5. What is wrong with the following ``proof'' that all horses are the same color?

   Let P(n) be the proposition that all the horses in a set of n horses are the same color. Clearly, P(1) is true. Now assume that P(n) is true, so that all the horses in any set of n horses are the same color. Consider any n+1 horses; number these as horses 1,2,3, ..., n, n+1. Now the first n of these horses all must have the same color, and the last n of these must also have the same color. Since the set of the first n horses and the set of the last n horses overlap, all n+1 must be the same color. This shows that P(n+1) is true and finishes the proof by induction.

• HW 3    (out May 16,   due May 24):   Chapter 2, page 50
  1. Exercise 11.
  2. Exercise 16, 17.
  3. Exercise 23, 24.
  4. Exercise 27.
  5. Suppose a and b are positive integers and x and y are integers such that ax+by = 65. What are the possibilities for gcd(a,b)? Explain.

• HW 4    (out May 24,   due May 31):   Chapter 2, page 51
  1. Exercise 39.
  2. Exercise 43.
  3. Problem 78.
  4. Repeat Exercise 27 (from HW3) using the prime factorization theorem. (Needless to day, you may not reproduce the proof in the solutions above!)
  5. Problem 93.

• Suggested problems (posted May 30, not to be handed in):
  1. Chapter 2, page 53, Problem 83.
  2. Factor the number 12827. Explain the property you used in factorizing the number and show your steps.
  3. Chapter 3, page 82, Exercise 2.
  4. Let N = 3⁷²⁹. What is the last digit in the decimal representation of N. What are the remainders when N is divided by 8, and 9?
  5. Chapter 3, page 82, Exercise 10, 11.

• HW 5    (out June 6,   due June 14):   Chapter 3, page 82
  1. What is the remainder when 3⁹⁵⁸ is divided by 107?
  2. Exercise 31.
  3. Exercise 35.
  4. Problems 93, 95(a).
  5. Exercise 54.

• HW 6    (out June 14,   due June 21):
  1. Chapter 3, Problem 61. Hint: 91 = 7 times 13. What is n⁹¹ congruent to modulo 7, and 13?
  2. Chapter 3, Problem 83.
  3. Chapter 7, Exercise 8.
  4. Chapter 7, Exercise 11, 12.
  5. Chapter 7, Exercise 22.

• HW 7    (out June 20,   due June 28):
  1. Chapter 7, page 181, Exercise 36.
  2. Let 0 < M < n, where n = pqr, and p,q,r are distinct primes. Suppose that a is congruent to 1 modulo (p - 1)(q - 1)(r - 1). Show that M^a is congruent to M modulo n.
  3. Chapter 7, page 181, Exercise 28.
  4. Chapter 7, page 181, Exercise 31.
  5. Chapter 8, page 218, Exercises 10, 12, 20, 22.

• HW 8    (out June 27,   due July 5):         Chapter 8, page 218
  1. (a) Exercises 31, 32. (b) Exercise 34.
  2. Exercises 94, 98, 100, 102.
  3. Exercise 87.
  4. Problem 113.
  5. Problem 120.

• HW 9    (out June 30,   due July 12):         Chapter 8, page 218
  1. Exercise 104.
  2. Exercise 38, 40, 42, 44.
  3. (a) Exercise 62, 64. (b) Exercise 88.
  4. Exercise 66.
  5. Exercise 110. (You need not attempt this one. It was cancelled on July 11)

• HW 10    (out July 12,   due July 19):
  1. Chapter 8, Exercise 110.
  2. Chapter 8, Problem 128.
  3. Find roots of x³ + 15 x² + 15 x + 14 in Z₇, the field of integers modulo 7.
  4. Chapter 3, Exercise 45.
  5. Chapter 3, Exercise 47.

• HW 11    (out July 18,   due July 26):      Chapter 9, page 262.
  1. Exercises 38, 40.
  2. Exercise 22.
  3. Exercise 24.
  4. Exercise 95.
  5. Exercise 98.