Due Mon, Aug 31 Homework 1 Read the syllabus and identify five items you think are important; all exam and quiz dates together count as one item. Then complete 1.4 through 1.9 and digest the surrounding text along the way.

Due Wed, Sep 2 Homework 2 Complete 1.10 through 1.14 and digest the surrounding text along the way. Then illustrate 1.12, 1.13, and 1.14 with actual numbers, as described in 1.19. Then, complete 1.20.

Due Fri, Sep 4 Homework 3 Revisit your proofs of 1.12, 1.13, and 1.14, and think about how each one could be improved by citing an earlier theorem in the sequence. Then read Supplement R on the Materials page through R.20. Most of the section on equivalence relations was discussed in class. The exercises and questions are optional but highly recommended; only R.9, R.13, R.17, R.19, and R.20 are to be submitted. R.9 and R.17 will not be presented.

Due Wed, Sep 9 Homework 4 Part 1: If you submitted a proof of Theorem R.19 and you are confident it is correct, you may skip this part. Otherwise: complete Exercise R.18 by writing out explicitly the set of ordered pairs. Then write a single sentence which describes, in terms of the blocks of $\Omega$, when two elements $a, b \in A$ are related; your sentence should make sense for any partition. Then revisit Theorem R.19 and write up a proof, following the outline that now appears below it in Supplement R on the Materials page. Part 2: Complete 1.15, 1.16, and 1.17.

Due Fri, Sep 11 Homework 5 Study for Quiz 1. Then complete Theorem 1.18. Give your best attempt at a proof, and try to identify exactly where you need a new tool.

Due Mon, Sep 14 Homework 6 Part 1: Read Supplement N on the Materials page. Complete Exercise N.2. Then read Appendix A and prove A.10, A.18, and A.21. All other items in Appendix A are optional and need not be submitted, but are recommended if this is your first time seeing proof by induction. Part 2: Complete 1.25 and 1.26 and digest the surrounding text along the way.

Due Wed, Sep 16 Homework 7 Complete 1.27 through 1.33 and digest the surrounding text along the way.

Due Fri, Sep 18 Homework 8 Complete 1.34 through 1.37 and 1.39 and digest the surrounding text along the way. For 1.35, try to be precise. Your description should say exactly what is computed at each step, explain why the algorithm terminates, and explain why its output is the greatest common divisor. What does it mean for the algorithm to have $k$ steps? Begin thinking about 1.38 (Note: this is a challenging problem), which will be assigned Friday.

Due Mon, Sep 21 Homework 9 Complete 1.38 and 1.40 through 1.45 and digest the surrounding text along the way. Give your best attempt at 1.44 before reading 1.45, since 1.45 is the answer.

Due Wed, Sep 23 Homework 10 An integer $c$ is cancellable modulo $n$ if for all integers $a$ and $b$, $ac \equiv bc \pmod{n}$ implies $a \equiv b \pmod{n}$. Revisit 1.45 and answer the following question: which integers are cancellable modulo $n$? Formulate your answer as an if and only if statement and prove your claim. Then complete 1.48, 1.53, and 1.54 and digest the surrounding text along the way. Questions and exercises along the way are suggested but optional. Finally, answer the following question: Does 1.51 imply 1.53? Justify your reasoning.

Due Fri, Sep 25 Homework 11 Study for Quiz 2. Start reading Ch 2. Complete 2.1, 2.3, 2.4, 2.5, and 2.7 and digest the surrounding text along the way.

Due Mon, Sep 28 Homework 12 Read the Strong Induction section of Supplement N.
Part 1: Let $p$ be a natural number with $p > 1$. Prove that the following are equivalent, using only the definitions:
(i) $p$ is prime.
(ii) For all $a, b \in \mathbb{N}$, if $p = ab$, then $a = 1$ or $b = 1$.
(iii) The only natural numbers dividing $p$ are $1$ and $p$.
Hint: It suffices to prove (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i). Why? Then revisit 2.7. If your proof used strong induction, prove it using the Well-Ordering Axiom, and vice versa. If you did not complete 2.7, or your proof used neither, prove it using either one.
Part 2: Complete 2.8 and 2.9 and digest the surrounding text along the way. For 2.8, Theorem 1.41 may be useful. Finally, answer the question after 2.9: if $1$ were a prime, why would the Fundamental Theorem of Arithmetic no longer be true?

Due Wed, Sep 30 Homework 13 Complete 2.8 and 2.9 if you have not already. Then, without using the Fundamental Theorem of Arithmetic, complete 2.26 and the following strengthening of 2.27: Let $p$ be a natural number with $p > 1$. Then $p$ is prime if and only if for all integers $a$ and $b$, if $p \mid ab$, then $p \mid a$ or $p \mid b$. This came up in class, but write a clean proof of your own. This adds a fourth characterization (iv) of what it means to be prime to the list (i)–(iii) from Homework 12. Finally, complete 2.28.

Due Fri, Oct 2 Homework 14 Part 1 (due Fri, Oct 2): Complete the following applications of the Fundamental Theorem of Arithmetic: Exercises 2.10, 2.11, and 2.14, Theorems 2.19 and 2.20, and Exercises 2.21 through 2.23. Digest the surrounding text along the way.
Part 2 (due Sat, Oct 3, 11:59 pm via Gradescope): Complete the True or False Submission sheet on the Materials page. Your work must be turned in on this sheet.

Due Mon, Oct 5 Homework 15 Read the section on the infinitude of primes and complete 2.32 through 2.35. Start thinking about 2.38, which may be challenging, and will be assigned Monday. Then read the section on the distribution of primes and complete 2.46. Start studying for the midterm, and remember to submit Homework 14 Part 2 via Gradescope by Saturday (which counts as studying for the exam).

Due Mon, Oct 12 Homework 16 Start reading Ch 3.
Part 1: Complete 3.1 through 3.6. Reduce modulo $n$ as you go rather than multiplying out large numbers, and justify each step using one of 1.12, 1.13, 1.14, or 1.18 (you do not need to write a formal proof). For 3.6, create your own example and test your technique.
Part 2: Complete 3.14 through 3.17 and digest the surrounding text along the way. You may skip 3.7 through 3.13. For 3.14, do not cite G.2; instead, use the Division Algorithm for natural numbers (1.26 and 1.27). Hint: if $a < 0$, apply it to $-a$.

Due Wed, Oct 14 Homework 17 Part 1: Revisit 3.14 and write a proof for $a \le 0$ (skip this if you already handled this case). Hint: if $a < 0$, apply the Division Algorithm for natural numbers to $-a$. Revisit 3.16 and 3.17 as well; you may skip these if you are confident in your proofs. For 3.17, think about the canonical representative of each $a_i$ (from 3.14). Can two of them be equal? In any case, come prepared to discuss these problems.
Part 2: Start linear congruences: complete 3.18 through 3.20 and digest the surrounding text along the way.

Due Fri, Oct 16 Homework 18 Prove: there are precisely $n$ equivalence classes modulo $n$, namely $[0], \ldots, [n-1]$. There are two precise statements to prove:

• At most $n$: every class is one of these. For all $a \in \mathbb{Z}$, there is $t \in \{0, 1, \ldots, n-1\}$ with $[a] = [t]$.
• At least $n$: no two of these are equal. For all $t, u \in \{0, 1, \ldots, n-1\}$, if $[t] = [u]$, then $t = u$.

Then complete 3.22 and 3.24. Part 3 of 3.24 is the significant part.

Due Mon, Oct 26 Homework 19 Revisit and submit a polished proof of 3.24. Note that 3.24.1 is just a restatement of 3.20. Write $d = (a,n)$ and suppose $x_0$ is a solution.
3.24.2 bundles two statements. Check that your proof establishes both:

• For every solution $x$, there exists $m \in \{0, \ldots, d-1\}$ such that $x \equiv x_0 + \frac{n}{d}m \pmod{n}$.
• For every $m \in \{0, \ldots, d-1\}$, the integer $x_0 + \frac{n}{d}m$ is a solution.

A good starting point is to prove the following statement: an integer $x$ is a solution if and only if $\frac{n}{d} \mid x - x_0$. Both statements above follow quickly from it.
3.24.3. 3.24.2 shows the solutions lie in at most $(a,n)$ classes mod $n$. Show that no two of $x_0 + \frac{n}{d}m$, $0 \le m \le d-1$, are congruent mod $n$, so there are exactly $(a,n)$ classes. Then cite the result guaranteeing that each class contains exactly one element of $\{0, \ldots, n-1\}$.