Homework for Math 300.02 Spring 2025

SHOW ALL YOUR WORK!!!

Problems are from the textbook.

• Assignment 1   (Due Thursday, February 6)
  • Exercise Set 1 page 20:   1 to 6, 9, 10, 12, 14, 24, 26, 28, 30, 62, 68, 69, 72.
  • 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, February 13)
  • Exercise Set 1 page 20:   39, 40, 41, 44, 46, 50, 51, 53, 55, 57, 62, 63, 64, 65, 66, 67, 69, 70, 73, 75, 76. Scanned copy of the homework problems.
  • Solutions to problems 24, 28, 44, 66.
  • Solution to Set 1 problem 75.
• Assignment 3   (Due Tuesday, February 25)
  • Exercise Set 2 page 50:   7, 8, 10, 11, 13, 14, 19, 20, 26, 27, 28, 31, 32, 73, 83, 84. (can be done after Lecture 4 on Feb 13) Scanned copy of the homework problems.
  • Exercise Set 2 page 50:   , 38, 44 ,48, 51. (Depends on Lecture 5 on Feb 18). Scanned copy of the homework problems.
  • Solutions to problems 20, 32, 38, 48.
  • Solutions to problems 10, 11, 14:   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 4   (Due Tuesday, March 4)
  • 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 (note, for example, that 7 and 11 are two consecutive odd primes, so consecutive means in the list of odd primes, not in the list of odd integers). Scanned copy of the homework problems.
  • Hint for 93: Prove it by contradiction.
  • Solutions to Set 2 problems 51, 68, 69, 70.
  • Solution to Set 2 problem 72.
  • Solution to 30: Every t=lcm(32,120)/32=15 minutes, since 32t should be a multiple of 120.
  • Solution to 93 (by contradiction): Assume that p and q are consecutive odd prime and that p+q has at most two prime divisors (not necessarily distinct). Then p+q is even and >= 3+5 and p+q=2r, where r is a prime. But r=(p+q)/2 is between p and q. This contradicts the fact the the two are consecutive primes.
• Assignment 5   (Due Tuesday, March 11)
  • Exercise Set 4 page 104:   14, 15, 8, 16, 17, 25, 28, 29, 30, 58, 62, 63 (see hint below). Scanned copy of the homework problems.
  • 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 problems 62, 63.
• Assignment 6   (Due Tuesday, March 25)
  • Exercise Set 4 page 104:   26, 34, 41, 45, 57, 73, 74, 76, 77.
  • Solutions to Set 4 problems 30, 34, 45, 57.
  • Solutions to problems 73, 74, 77.
• Assignment 7   (Due Tuesday, April 1)
  • Exercise Set 3 page 82:   2, 3, 5, 6, 7,8,10,19 (justify your answers), 23,25, 56 (the second statement means x is congruent to y OR to -y modulo p), 68.
  • Solutions to Set 3 problems 3, 6, 10, 30. and 56.
• Assignment 8   (Due Tuesday, April 8)
  • Exercise Set 3 page 82:   29, 30, 31.
  • Exercise Set 3 page 82:   (depend on Thursday's lecture) 34, 35, 39, 42, 44,45, 46, 47, 48.
  • Solutions to problems 35, 44, 47, 48.
• Assignment 9   (Due Tuesday, April 15)
  • Exercise Set 3 page 82:   50, 52 (start with the second congruence), 55.
  • 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.
  • 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.
• Assignment 10   (Due Tuesday, April 22)
  • Exercise Set 3 page 82:   98, 99, 101.
  • Recommended (optional) extra problem related to the Euler-Fermat Theorem.