Homework for Math 300 Section 3 Fall 2023

SHOW ALL YOUR WORK!!!

Problems are from the textbook.

• Assignment 1   (Due Thursday, September 14)
  • Exercise Set 1 page 20:   1 to 6, 9, 10, 12, 14, 24, 26 to 30, 39, 40, 41, 44, 46, 50, 51, 53. Scanned copy of the homework problems. You need to purchase the textbook for future assignments.
  • Solutions to problems 24, 28, 44, 66.
• Assignment 2   (Due Thursday, September 21)
  • Exercise Set 1 page 20:   55, 57, 62, 63, 64, 65, 66, 67, 69, 70, 73, 75, 76. Scanned copy of the homework problems.
  • Exercise Set 2 page 50:   7, 8, 10, 11, 13, 14. Scanned copy of the homework problems.
  • Solution to Set 1 problem 75.
  • Solutions to graded problems:   10) If ac|bc and c not equal zero, then a|b Proof: If ac|bc, then there exists an integer q such that bc=acq. It follows that b=aq, since c is non-zero. Hence, a|b, by definition.
    11) Let d=|d|u, where u is 1 or -1. a=gcd(a,b)q_1, so ad=|d|gcd(a,b)(q_1u), hence |d|gcd(a,b) divides ad. b=gcd(a,b)q_2, so bd=|d|gcd(a,b)(q_2u), hence |d|gcd(a,b) divides bd. We conclude that |d|gcd(a,b) is a common divisor. If a=0 and b=0, both sides of the equality gcd(ad,bd)=|d|gcd(a,b) are zero, hence the equality holds. The same holds if d=0. Assume a and d are not zero. Then |d|gdc(a,b) is not zero. Write gcd(a,b)=ax+by, for some integers x,y (possible by the extended euclidean algorithm. Then |d|gcd(a,b)=ax|d|+by|d|=ad(ux)+bd(uy). If c is a common divisor of ad and bd, then c divide the right hand side above, by Prop. 2.11 (i). Hence, it divides |d|gcd(a,b). Hence, c<=|d|gcd(a,b), by Prop. 2.11 (iv) (where we used that |d|gdc(a,b) is not zero). We conclude that |d|gcd(a,b) is the greatest common divisor.
    14) Compute gcd(616,427) Answer: 616=1x427+189, 427=2x189+49, 189=3x49+42, 49=1x42+7, 42=6x7+0. Hence, gcd(616,427)=7.
• Assignment 3   (Due Thursday, September 28)
  • Exercise Set 2 page 50:   19, 20, 26, 27, 28, 31, 32, 38, 44 ,48, 51, 73, 83, 84. Scanned copy of the homework problems.
  • Solutions to problems 20, 32, 38, 48.
• Assignment 4   (Due Thursday, October 5)
  • Let p be an odd prime. Suppose that p=q+r, where q and r are primes. Prove that p-2 is a prime. Hint: Consider the parity (even or odd) of q and r.
  • Exercise Set 2 page 50:   30, 68, 69, 70, 72, 78, 85, 87, 93. Scanned copy of the homework problems.
  • Solutions to Set 2 problems 51, 68, 69, 70.
  • Solution to Set 2 problem 72.
• Assignment 5   (Due Thursday, October 19)
  • Exercise Set 4 page 104:   14, 15, 8, 16, 17, 25, 28, 29, 30, 58. Scanned copy of the homework problems.
  • Exercise Set 4 page 104:   62, 63 (see hint below), 34, 41, 45, 57.
  • Hint for 63: Method 1: Prove, by induction, that f_n=a^{n-1}+a^{n-2}b+...+b^{n-1}, for n>2, observing that a+b=1, ab=-1, and a-b=square root of 5. Method 2: (easier) Prove, by induction, that f_n=(a^n-b^n)/sqrt{5}. In the induction step use f_{n+1}=f_n+f_{n-1}=(a+b)f_n+f_{n-1} and notice a cancelation.
  • Solutions to Set 4 problems 14, 16, 17.
  • Solutions to Set 4 problems 30, 34, 45, 57.
  • Solutions to problems 62, 63.
• Assignment 6   (Due Thursday, October 26)
  • Exercise Set 4 page 104:   73, 74, 76, 77.
  • Solutions to problems 73, 74, 77.
  • Exercise Set 3 page 82:   1 to 6 (all) (for problem 4 do only base 10).
• Assignment 7   (Due Thursday, November 2)
  • Exercise Set 3 page 82:   7,8,10,19 (justify your answers), 23,25,29,30, 31, 56, 67, 68.
  • Solutions to Set 3 problems 3, 6, 10, 30. and 56.
• Assignment 8   (Due Thursday, November 9)
  • Exercise Set 3 page 82:   28, 34, 35, 39, 42, 44,45, 46, 47, 48, 50, 52 (start with the second congruence), 55.
  • Solutions to problems 35, 44, 47, 48.
• Assignment 9   (Due Thursday, November 16)
  • Exercise Set 3 page 82:   61 (see hint below), 82, 84 (credit will be given only for a solution using the Chinese Remainder Theorem, see hint below), 87, 90, 98, 99, 101.
  • Extra problem related to the Euler-Fermat Theorem.
  • Hint for 61: For the first question: Prove first that if n^91 is congruent to n^7 both modulo 7 and modulo 13, then n^91 is congruent to n^7 modulo 91 (see Proposition 3.64). Then use Fermat's Little Theorem as well as its Corollary 3.44. Note that the argument proves a more general statement: If p and q are two distinct primes and q is congruent to 1 (mod p-1), then n^(pq) is congruent to n^p (mod pq). You may find it easier to prove the more general statement and then apply it. For the second question, consider first the question whether n is congruent to n^91 (modulo 13).
  • Hint for 84: Follow example 3.67. Note however that the equation [x^3]=[17] has three distinct solutions in Z_9, while that equation has a unique solution in Z_11. You will thus need to solve three sets of two simultanuous congruences. One of them could be solved using Prop 3.64 without any computations.
  • Solutions to problems 61, 82, 84, 98, 99, 101.
  • Exercise Set 5 page 121:   2 (addition was done in class and can be omitted), 33 (first introduce the equivalence relation, next prove that it is indeed an equivalence relation, then define addition on the set of equivalence classes, and finally show that addition is well defined), 37 (see hint below).
  • Hint for Set 5 problem 37: In Part b, use Proposition 5.11 and Part a of this excercise. Prove part c by contradiction using part b. Treat the statement ``square root of p is irretional'' as the statement ``there does not exist a rational number whose square is p''.
  • Solutions to Set 5 problems 33 and 37.
• Assignment 10   (Due Thursday, November 30)
  • A problem on equivalence relations:   Fix a positive integer n larger than 1. Recall that two square nxn matrices A and B are similar, and we write A ~ B, if there exists an invertible matrix P, such that B=P^{-1}AP. Prove that similarity is an equivalence relation. Caution: Matrix multiplication is not commutative.
  • Exercise Set 6 page 153:   1 to 4, 15, 17, 33, 34 (see hint below).
  • Hint for Set 6 problem 34: You should get precisely 6 functions. Compute the compositions f,g,ff,gg,fg,gf,fgf,gfg,fgfg,gfgf. You will discover 4 identities due to which the previous 10 compositions yield only 6 function. Next use these four identities to prove by induction on n that if h is a composition h=h_1h_2...h_n of n functions h_i, each of which is equal to either f or g, then h is equal to one of the 6 functions found above.
  • Exercise Set 6 page 153:   5, 6, 18, 19, 21, 39, 43.
  • Solutions to Chapter 6 problems 6 and 34.
  • Solutions to Chapter 6 problem 43.
• Assignment 11   (Due Thursday, December 7)
  • Exercise Set 6 page 153:   117 (see hint below), 119.
  • Hint for problem 117: First show that there exists a positive integer s, such that rs is congruent to 1 (mod p-1). Then let g:Z_p -> Z_p be given by g[x]=[x^s]. Use Fermat's Little Theorem to prove that g is the inverse of f (treat the congruence class of 0 modulo p separately).
  • Solutions to Chapter 6 problem 117.
  • Exercise Set 6 page 153:   44 (in other words, prove that having the same cardinality is an equivalence relation),45,46,47,48 (use proof by induction on the cardinality of X),71, 99.
  • Solutions to Chapter 6 problems 47, 45,48.
  • Exercise Set 6 optional problem (not to be handed in):   Given sets A and B define the product #(A)#(B) of their cardinalities to be the cardinality #(AxB) of their product AxB={(a,b) such that a belongs to A and b belongs to B}. Show that for finite non-empty sets A and B the product #(A)#(B) agrees with the product of the integers #(A) and #(B) defined on page 138 in the text. In other words, given a bijection f:P_k -> A and g:P_n ->B, show that there exists a bijection h:P_{kn}->AxB. Prove that the function h you constructed (in terms of f and g) is indeed a bijection. Hint: Consider first the special case where A=P_k and B=P_n. Note that an element of P_kxP_n is a pair (i,j) that represents a position in a k by n matrix. In this case let h:P_kn -> P_kxP_n be the counting of elements of P_kxP_n going through the matrix row by row. In other words, h(x)=(i,j), where i and j are the unique positive integers satisfying the three conditions (1) 1<= i <= k, (2) 1<= j <=n, and (3) x=(i-1)n+j. For h to be well defined you need to prove the existence and uniqueness of the pair (i,j) as above. Compare with the proof of the Division Algorithm 2.12 in the text, which proves a similar statement. Then prove that h is a bijection. Next reduce the general case to the special case using the given bijections f and g.
  • Exercise Set 6 page 153:   102, 103, 104 (see comment below), 105 (Hint: use problem 103).
  • Comment/hint for problems 103 and 104: The definition in the text for #(A)+#(B) assumes that A and B are disjoint sets. So it does not apply when A=B, as in problem 103, or when A contains B as in problem 104. For these problems use the following more general definition:
    #(A)+#(B)=#(Ax{1} union Bx{2}).
    Above Ax{1} is the set of pairs {(a,1) : a is an element of A} and Bx{2} is the set of pairs {(b,2) : b is an element of B}. The sets Ax{1} and Bx{2} are clearly disjoint and there is an obvious bijection between A and Ax{1} and similarly between B and Bx{2}. For problem 103 construct a bijection f from Px{1} onto the positive odd integers. Constract also a bijection g from Px{2} onto the positive even integers. Then use a split definition
    h(n,i)= f(n), if i=1, and h(n,i)=g(n), if i=2,
    in order to construct a bijection h from (Px{1} union Px{2}) onto P.
  • Exercise Set 6 page 153:   Extra problem on cardinality.
  • Solutions to the extra problem:
    Part 1: f: P(A U B) -> P(A) x P(B) sends a set S to (S_1,S_2), where S_1=intersection of S with A, S_2=intersection of S with B. f^{-1} is g(S_1,S_2)= union of S_1 and S_2. One checks that the compositions fg and gf are the identities.
    Part 2: #(P(N) x P(N)) = #(P(N disjoint union N)) by part 1, and the latter is equal to #(P(N)), since by Problem 103 there is a bijection between N x {1,2} :=(N disjoint union N), and N itself and this bijection induces a bijection between the power sets (a fact proven in the last recitation).
• Assignment 12   (Not to be handed in, but the material on permutations is covered in the final exam)
  • Exercise Set 6 page 153:   72, 74, 75, 76, 77, 78, 79, 80, 113, 114, 115 (use the composition table on page 152), and Extra problem on permutations.
  • Solutions to Chapter 6 problems 72,76,77,80.