Proofs (and Number Theory)

Syllabus

Calendar

Your syllabus has a rough calendar of what we will be covering each class. After each class I will post what we were actually were able to cover here:

…
12/4 – Today we covered the Fundamental Theorem of Arithmetic and the Chinese Remainder Theorem. On Thursday we will cover Euler’s \(\phi\)-function and Euler’s Theorem. I have updated the notes I typed up so that they cover all the number theory we are covering this semester plus some extras: Proofs in Number Theory DRAFT.
11/27 – Today we launched into a more in depth discussion of number theory. We looked at the Euclidean Algorithm used for finding the g.c.d. of two integers and which we can use to help identify coefficients \(x\) and \(y\) such that \(d=(a,b)=ax+by\), which we know is possible from Bezout’s Lemma. We also saw that given a linear combination \(c=ax_0+by_0\) all other linear combination which equal \(c\) have coefficients \(x_t=x_0+t\cdot b/(a,b)\) and \(y_t=y_0-t\cdot a/(a,b)\). Finally, we discussed the Fundamental Theorem of Arithmetic and we will pick up there on Thursday. Rough draft notes on most of the number theory we have covered and weill cover can be found here: Proofs in Number Theory DRAFT.
11/20 – Exam on Mathematical Induction
11/16 – Ran through the proof of Bezout’s Lemma which depaned on the Well Ordering Principle (W.O.P.) and then used it to show that “Given a prime integer \(p\) and another integer \(n\), \(p|n\) if and only if \(p|n^k\) for all k,” that required induction.
11/13 – You got back the indirect proofs exams, the redos are due next week. Please recall that all out of class work should be typed and in complete sentences unless very specifically stated otherwise. We started discussing proofs by induction. We did four complete proofs and discussed some other results we would like to look at. In particular we would like to show that “Given a prime integer \(p\) and another integer \(n\), \(p|n\) if and only if \(p|n^k\) for all k.” In order to help us do this we will learn some more number theory, in particular we will prove Bezout’s Lemma.
11/9 – Indirect Proofs Exam
11/6 – We did a number of examples of proof by contradiction and proof by contrapositive ahead of the exam on Thursday
110/30 & 11/2 – We discussed proof by contradiction and proof by contrapositive.
10/26 – Exam on Direct Proofs
10/23 – We finished discussing direct proofs and touched on common mistakes in proofs.
10/19 – Today we did additional examples of direct proofs as well as some examples of proofs by cases. We will due a little more of this next class as well as discussing common mistakes and answering questions ahead of the exam.
10/16 – The exam were handed back today, as before redos, if you have any, are due a week from today on the 10/23. In class we looked at some more examples of direct proof. Next class we will discuss this some more as well as pointing out common mistakes that are easy to make.
10/12 – Definitions, Theorems, and Proofs Exam
10/9 – Today we looked at a couple more lemmas related to divisibility while we reviewed ideas about reading definitions, theorems, and proofs. This was in preparation for the exam on Thursday.
10/2 & 10/5 – We spent some more time discussing the Conjecture packet on Monday, in particular how we can try and find new results from simpler old results or from examples we have looked at. On Thursday we discussed some points from the problem solving exercises and then worked through proof(s) of “Theorem: Given \(a,b,c\in\mathbb{Z}\), \(c|a\) and \(c|b\) if and only if \(c|(ax+by)\) for all \(x,y\in\mathbb{Z}\).” In particular we saw how looking at examples and non-examples helped us understand how to prove the theorem. This was our first instance of a direct proof, we will continue this on Monday. You should read through Chapter 19 as reinforcement of the ideas we have been discussing related to reading and understanding theorems and proofs.
9/28 – Reading Mathematics (Take 2) – Conjecture Exercises Handout – We got through the first page or two of this handout after discussing the problem solving extra credit from the exam and the importance of trying something. Exam redos are due on Thursday 10/5.
9/25 – Reading Writing and Statements Exam
9/21 – We spent today reviewing material from MAT 141 on Logic and Implications.
9/18 – We looked at material from chapter 5 today on Polya’s Four Step Problem Solving Process. These ideas are key to understanding how to approach solving a problem that is genuinely new to you rather than exercises to which you find solutions using well established algorithms. These are the steps you need to use when you work on the problem solving assignment due on 10/2/2023, the details are below in the assignment section.
9/14 – We looked at the Sample Calculus Problem and Sample Systems Problem with Errors to discuss proofreading and rewriting work. You can look at and ask questions about the Sample Trigonometry Problem for extra practice. You have similar work dues next Thursday, that is listed below with the other assignments.
9/11 – We worked through sections 2 and 3 of the Writing Up Mathematics Packet, and looked at section 4. You need to finish sections 5 and 6 for Monday the 18th; al this work needs to be typed.
9/7 – Today was our first discussion about Reading Mathematics (Take 1, see exercises (iii) and (iv) p.19). We basically completed exercises (iii) and (iv) from chapter 2. We also discussed how you should work your way through mathematics as your reading it; engage in active reading with a pencil and paper at your side as you read. Skim through chapter 2 and then complete your first assignment by reading through the copy of chapter 1 posted below.
- Strang’s Calculus – Newton’s Method
- Apex Calculus – Newton’s Method
- OpenStax Calculus – Newton’s Method
8/31 – Today we went over the syllabus and then used the 1st Day Opening Activity to discuss how mathematical ideas build on each other and a little about how we know when something is true or false.

Assignments

Unless specifically specified otherwise, all assignments must be typed and in complete sentences. Proper submission formatting may count for up to 10% of the assignment grade.

Due 9/11/2023 – Reading Assignment: Hand in your annotated copy of chapter 1 from your text, and your work for problem (iv) on page 12. Recall that for this you should be completing/explaining the underlined statements and answering included questions. This assignment does not need to be typed, most of it you can complete by writing directly on a copy of chapter 1. (This is a variation on exercise (i) on p.19)
Due 9/18/2023 – Writing Up Mathematics Assignment.
Due 9/21/2023 – Rewriting Assignment: Rewrite these poorly written out solutions: Hey isn’t this good enough Prof?
Due 10/02/2023 – Problem Solving Assignment: Demonstrate that you have used all of Polya’s steps by solving these Chapter 5 problems (For this assignment turn in your written rough work along with your typed final solution): p.49 (iv), and (vi),
Due 10/09/2022 – Conjecture Exercise : This assignment does not need to be typed, in fact much of it you can complete by writing directly on a copy of the Conjecture Exercise handout, though you might want to do scrap work on the side before writing your final solutions.
Due 10/26/2023 – Direct Style Proofs: From the text: p.146 – (ii); p.153 – (ii); p.159 – (i) and (vii)
Due 11/9/2023 – Contradiction and Contrapositive Proofs: From the text:
- p.164 – (iv); p. 165 – (xii) (Hint: First prove the lemma: If \(n^3\) is even, then \(n\) is even.);
- p. 183 – (iii) (Hint: Look at p.165 – (i)).
Due 11/20/2023 – Induction Proofs: From the text:
- p.172 – (ii), (vii), (iii) (Prove (iii) once directly and then prove (iii) again using (vii)) ;
- Extra Credit p.173 – (vi) or (viii)
Due 12/15/2023 by 4pm – Number Theory Assignment from the text:
- p. 194 – (ii), (iv); p.206 – (ii), (iv)ab; p.216 – (xi)bd, (xiv);
- Extra Credit p.207 (viii)
Due 12/15/2023 by 4pm – Proofs Portfolio: Remember that this must contain an example of: direct proof, proof by cases, proof by contradiction, proof by contrapositive, and proof by induction. For each proof you should include at least two drafts; one that you completed earlier in the semester that I commented on, and at least one revision of that.
Due 12/15/2023 – Extra Credit What is Mathematics? Assignment: Read this article What is Mathematics? by Jenny Quinn (MAA Focus Vol, 42 No. 4), then write a brief reflection on your own thoughts. This should be typed, double spaced, with 1 inch margins, and about a page long. Be sure to include …
- Comments on your past experience with math.
- What sort of things you think about when you are “doing math.”
- What you think math is based on your experiences and on what you personally got out of the article.
Due 12/15/2023 – Extra Credit Induction Assignment: Complete this Scaffolded Induction Exercise Extra Credit for upto +2% on your final grade.

Exams

Monday 9/25 – Exam 1: Reading, Writing, and Statements covers chapters 1 through 5
Thursday 10/12 – Exam 2: Definitions, Theorems, and Proofs will cover the material from chapter 6 through 18 with an emphasis on understanding implications, quantifiers, and reading theorems and proofs.
Thursday 10/26 – Exam 3: Direct Proofs will cover direct proofs, proofs by cases, divisibility, modular equivalence, and the division algorithm.
Thursday 11/9 – Exam 4: Indirect Proofs will cover proofs by contradiction and by contrapositive.
Monday 11/20 – Exam 5: Induction will cover proofs by induction, you need to know the P.M.I., Strong Induction, the general format of a proof by induction.
Thursday 12/14 @ 11am (During Finals!) – Exam 6: Number Theory will cover:
- Divisibility
- Division Algorithm
- Well Ordering Principle
- Fundamental Theorem of Arithmetic
- Greatest Common Divisor and Least Common Multiple
- Euclidean Algorithm
- Chinese Remainder Theorem
- Wilson’s Theorem
- Euler’s \(\phi-function\) and Euler’s Theorem (Fermat’s Little Theorem)

Dr. Charles Rocca

Professor of Mathematics

Proofs (and Number Theory)

Syllabus

Calendar

Assignments

Exams

Links and Handouts

Typesetting Math