Contact Information: My contact information is posted on my web page.
Course Description: Investigation of properties of the natural numbers. Topics include mathematical induction, factorization, Euclidean algorithm, Diophantine equations, congruences, divisibility, multiplicative functions, and applications to cryptography.
Prerequisites: CS 3000 or MATH 3050
Special Needs: If you have physical, psychiatric, or learning disabilities that require accommodations, please let me know as soon as possible so that your needs may be appropriately met.
Class Format:
Reading and Videos: Students will learn the mathematical content for the course by reading the book and watching instructional videos developed by the instructor, Mark Barsamian.
In-Person Meetings: Held Mon,Wed,Fri 10:45 - 11:40am in Morton 218, the class meetings will be used mainly for discussion. Attendance is required.
Final Exam Date: Mon Dec 5, 2022 from 10:10am to 12:10pm in Morton 218
Syllabus: This web page replaces the usual paper syllabus. If you need a paper syllabus (now or in the future), unhide the next three portions of hidden content (Textbook, Grading, Learning Objectives) and then print this web page.
Textbook Information:
Textbook Information for 2022 - 2023 Fall Semester MATH 3070
Title: Discrete Mathematics with Applications, 4^{th} Edition
Author: Suzanna Epp
Publisher: Brooks/Cole (Cengage Learning), 2010
ISBN-10: 0495391328
ISBN-13: 978-0495391326
The book is widely-available at a huge range of prices. Save money by getting a used copy. (And note that we are not using the most recent edition of the text. This should help make used copies quite cheap.)
List of all Suggested Exercises:
Suggested Exercises for 2022 - 2023 Fall Semester MATH 3070
The Suggested Exercises, shown in the list below, are selected from the textbook. These problems are not to be turned in and are not part of your grade. But in order to learn the material covered in the course, you should do as many of the suggested problems as possible and keep your solutions in a notebook for study
Epp 4th Edition Section 1.1 Variables: #2,6,11,13
Epp 4th Edition Section 2.1 Logical form and Logical Equivalence: #8,22,26,28,33,34,42,45
(video)
(notes)
"Every vehicle in the Morton Hall parking lot is a Ford".
What is ~ A?
More generally, let A be the universal statement
$$\forall x \in D \left( Q(x) \right)$$
What is ~ A ?
Lucas Fernandes CP1:
Let B be the statement
"There exists a vehicle in the Morton Hall parking lot that is a Ferrari".
What is ~ B?
More generally, let B be the existential statement
$$\exists x \in D \left( Q(x) \right)$$
What is ~ B?
Luke Haskell CP1:
Let C be the universal conditional statement
$$\forall x \in D \left( IF \ \ P(x) \ \ THEN \ \ Q(x) \right)$$
What is the negation, ~ C?
As a specific example, let C be the following universal conditional statement:
$$\forall x \in \mathbb{R} \left( x \lt 7 \rightarrow x^2 \lt 49\right)$$
Find the negation ~ C.
For the specific example given, which is true, C or ~ C ? Explain.
Ethan Levingston CP1: Consider again the universal conditional statement C that Luke discussed earlier:
$$\forall x \in \mathbb{R} \left( x \lt 7 \rightarrow x^2 \lt 49\right)$$
Write the converse, contrapositive, and inverse of C
Consider the four statements:
original statement C
converse of C
contrapositve of C
inverse of C
Which are true and which are false? Explain.
Jennifer Lewis CP1: Let S be the following universal conditional statement:
$$\forall n \in \mathbb{Z} \left(IF \ \frac{6}{n} \ is \ an \ integer, \ THEN \ \ n=2 \ or \ n=3\right)$$
Write the converse, contrapositive, inverse, and negation of S
Consider the five statments:
original statement S
converse of S
contrapositve of S
inverse of S
negation of S
Which are true and which are false? Explain.
Week 3 (Mon Sep 5 through Fri Sep 9)
Mon Sep 5 is Labor Day Holiday: No Class
Wed Sep 7:
Section to Discuss: 3.3 Statements with Multiple Quantifiers
Daniel Lipec CP1: Changing the order of multiple quantifiers.
Statement B is obtained by switching the order the quantifiers of Statement A.
$$\text{Statement A: }\forall x \in \left( \exists y \in \mathbb{Z} \left(x+y=0\right) \right) $$
$$\text{Statement B: } \exists y \in \mathbb{Z} \left( \forall x \in \mathbb{Z} \left(x+y=0\right) \right) $$
Answer these questions.
Which of the statements are true ? (one or both ) Explain.
One of the two statments is famous property of the Integers. Which statement? What is the name of the property? Explain.
Find the negation of any of any of the statements that are false.
Bradey LounsburyCP1: Changing the domain in quantifiers.
Consider the following Statement S..
$$\text{Statement S: }\forall x \in D \left( \exists y \in D \left( xy=1 \right) \right) $$
Write the negation for S.
Is Statement S true when \(D = \mathbb{Z}\)? Explain.
Is Statement S true when \(D = \mathbb{R}\) ? Explain.
Is Statement S true when \(D = \mathbb{R}^+\) ? Explain.
Bryce NicholsonCP1: Interchanging \( \forall \) and \( \exists \) in multiple quantifiers.
Consider Statement A and Statement B, which is obtained by interchanging \( \forall \) and \( \exists \) in the quantifiers of Statement A.
$$\text{Statement A: }\forall x \in \mathbb{Z} \left( \exists y \in \mathbb{Z} \left( x \lt y \right) \right) $$
$$\text{Statement B: }\exists x \in \mathbb{Z} \left( \forall y \in \mathbb{Z} \left( x \lt y \right) \right) $$
Is either of these statements true ? Explain.
Brittany Poss CP1: Interchanging x and y in the quantifiers.
Consider Statement A and Statement B, which is obtained by interchanging x and y in the quantifiers of Statement A.
$$\text{Statement A: }\forall x \in D \left( \exists y \in D \left( y=3x+2 \right) \right) $$
$$\text{Statement B: }\forall y \in D \left( \exists x \in D \left( y=3x+2 \right) \right) $$
Answer the following questions.
Let the domain \(D\) be the set \(\mathbb{R}\). Is either of the statements A, B true ? Explain.
Let the domain \(D\) be the set \(\mathbb{Z}\). Is either of the statements A, B true ? Explain.
Clair Schmidt CP1: Choosing correct order for symbols to create a true statement.
You find thirteen cards scattered on the ground. They have the following symbols on them:
Assemble the cards in an order that makes a correct statement. Explain.
Quiz Q02 on Wed Sep 7 Covering Sections 2.3, 3.1, and 3.2
20 Minutes at the end of class
Similar to Suggested Exercises from Sections 2.3 and 3.2.
Fri Sep 9:
Section to Discuss: 3.4 Arguments with Quantified Statements
Homework: H03.4: 3.4#4,11,13,15,17,18,20,22,26
Class Presentations: tba
Week 4 (Mon Sep 12 through Fri Sep 16)
Exam X1 on Mon Sep 12 Covering Chapters 1,2,3
The exam is the full class period.
No calculators, books, or notes
The Exam is typeset on 4 pages, printed on front & back of 2 sheets of paper. But page 4 is a table of Valid and Invalid Argument Forms, so the actual questions on the Exam occupy only 3 pages. This makes the Exam roughly 3 times the length of a Quiz.
The exam is six questions.
A question involving DeMorgan's laws and/or the negation of a Conditional Statement. (Concepts from Section 2.1 and 2.2)
A question involving DeMorgan's laws and/or the negation of a Conditional Statement. (Concepts from Section 2.1 and 2.2)
A question about logical equivalence of statement forms. (Concepts from Section 2.2)
A question about logical equivalence of statement forms. (Concepts from Section 2.2)
A question about statements with multiple quantifiers, and negations of those statements. (Concepts from Section 3.3)
A question about valid and invalid arguments. (Concepts from Section 3.4)(A table of Valid and Invalid Argument Forms will be provided.)
Wed Sep 14:
Section to Discuss: Epp 4th Edition Section 4.1 Direct Proof and Counterexample I: Introduction:
Video for Epp 5th Edition Section 4.1 = Epp 4th Edition Section 4.1:
(Video)
(Notes)
Video for Epp 5th Edition Section 4.2 = more topics from Epp 4th Edition Section 4.1:
(Video)
(Notes)
Class Presentations for Wed Sep 14
Jake Schneider CP1:
Is 0 even ? Explain
Can negative numbers be even ? Can they be odd ? Explain.
Are even & odd opposites? That word, opposites, is not really a defined term in our course. A better question would be, are even & odd the negation of one another? That is, is every integer either even or odd? Explain.
Assume that \(r\) and \(s\) are particular integers (a) is \(4rs\) even ? (b) is \(6r+4s^2+3\) odd? Explain.
Roman Simkins CP1: Prove or disprove: \(\forall n \in \mathbb{Z} \left(\text{If } n \text{ is odd then } \frac{n-1}{2} \text{ is odd.}\right) \)
Fri Sep 16:
Section to Discuss: Epp 4th Edition Section 4.1 Direct Proof and Counterexample I: Introduction:
Video for Epp 5th Edition Section 4.1 = Epp 4th Edition Section 4.1:
(Video)
(Notes)
Video for Epp 5th Edition Section 4.2 = more topics from Epp 4th Edition Section 4.1:
(Video)
(Notes)
Class Presentations for Fri Sep 16
Grace Smith CP1:
Is 1 prime ? Explain.
Can negative numbers be prime? Can they be composite? Explain.
Are prime & composite opposites? That word, opposites, is not really a defined term in our course. A better question would be, are prime & composite the negation of one another? That is, is every integer either prime or composite? Explain.
If \(r\) and \(s\) are positive integers, is \(r^2+2rs+s^2\) prime or composite or neither? Explain.
Rashid Al Busa'idi CP1: Prove or disprove the following statements.
\(\exists n \in \mathbb{Z} \left(2n^2-5n+2 \text{ is prime.}\right) \)
\(\forall n \in \mathbb{Z} \left(2n^2-5n+2 \text{ is composite.}\right) \)
\(\forall n \in \mathbb{Z} \left(2n^2-5n+2 \text{ is prime OR } 2n^2-5n+2 \text{ is composite.}\right) \)
Nicole Strang CP1: Consider Statement \(S\): \(\forall n \in D\left(n^2-n+11 \text{ is prime.}\right) \)
Let \(D=\{1,2,3,4,5,6,7,8,9,10\}\). Prove that \(S\) is true using the method of exhaustion.
Now let \(D=\mathbb{Z}^+\). Is \(S\) true or false? Explain.
Week 5 (Mon Sep 19 through Fri Sep 23)
Mon Sep 19:
Section to Discuss: Epp 4th Edition Section 4.1 Direct Proof and Counterexample I: Introduction:
Video: Video for Epp 5th Edition Section 4.3 = Topics from Epp 4th Edition Section 4.2 (link to video) (Link to Notes)
Class Presentations for Fri Sep 23
Daniel Lipec CP02:
Consider the list of expressions below. Which represent real numbers? Which represent rational numbers. Explain. (If you say that an expression represents a rational number, then you should give the ratio of integers that equals that expression.)
7
-5
0
0/5
5/0
753.86234
753.86234234234… (Decimal repeats starting in the 3rd decimal place.)
Bradey Lounsbury CP02:
What is the Zero Product Property ?
Write the Zero Product Property as a universal conditional statement. Then write the contrapositive of that universal conditional statement.
Why is the Zero Product Property introduced in Epp 4th Edition Section 4.2 on Rational Numbers? Give an example of how the Zero Product Property is used in Section 4.2.
Bryce Nicholson CP02: Consider the statement "The square of any rational number is rational"
Rewrite the statement more clearly using quantifiers.
Prove or disprove the statement.
Brittany Poss CP02: Consider the statement "The product of any two rational numbers is rational"
Rewrite the statement more clearly using quantifiers.
Prove or disprove the statement.
Clair Schmidt CP02: Consider the statement "The quotient of any two rational numbers is rational"
Rewrite the statement more clearly using quantifiers.
Prove or disprove the statement.
Week 6 (Mon Sep 26 through Fri Sep 30)
Mon Sep 26:
Section to Discuss: Epp 4th Edition Section 4.3 Direct Proof and Counterexample III: Divibility
Homework: Problems from Epp 4th Edition Section 4.3 # 2,3,4,12,15,16,19,20,24,26,27,28,29,30,32,36,37,38,41,47,48
Video: Video for Epp 5th Edition Section 4.4 = Topics from Epp 4th Edition Section 4.3 (link to video) (Link to Notes)
Class Presentations for Mon Sep 26
Jake Schneider CP02:
Do the symbols 5 / 7 and 5 | 7 mean the same thing ? Explain.
Do the symbols 2 / 6 and 2 | 6 mean the same thing ? Explain.
Frick and Frack are arguing. Frick says that 3 / 0 is undefined. Frack says that 3 | 0 is true. Who is right ? Explain.
Donkey and Elephant are arguing. Donkey says that 0 / 5 is zero. Elephant says that 0 | 5 is false. Who is right ? Explain.
Roman Simkins CP02: Consider the statement "For all integers a, b, and c, if a | b and a | c, then a | b-c."
Write the statement formally, using symbols for the quantifier.
Write the negation of the statement formally, using symbols for the quantifier.
Prove or disprove the statement.
Grace Smith CP02: Consider the statement "For all integers a, b, and c, if ab | c then a | c and b | c."
Write the statement formally, using symbols for the quantifier.
Write the negation of the statement formally, using symbols for the quantifier.
Prove or disprove the statement.
Nicole Strang CP02: Consider the statement "For all integers a, b, and c, if a | bc then a | b or a | c."
Write the statement formally, using symbols for the quantifier.
Write the negation of the statement formally, using symbols for the quantifier.
Prove or disprove the statement.
Rashid Al Busa’idi CP02: Consider the statement "For all integers a, b, and c, if a | b then a^{2} | b^{2}."
Write the statement formally, using symbols for the quantifier.
Write the negation of the statement formally, using symbols for the quantifier.
Prove or disprove the statement.
Wed Sep 28:
Section to Discuss: Epp 4th Edition Section 4.3 Direct Proof and Counterexample III: Divibility
Homework: Problems from Epp 4th Edition Section 4.3 # 2,3,4,12,15,16,19,20,24,26,27,28,29,30,32,36,37,38,41,47,48
Video: Video for Epp 5th Edition Section 4.4 = Topics from Epp 4th Edition Section 4.3 (link to video) (Link to Notes)
Class Presentations for Wed Sep 28
Gretchen Angst CP03:
Suppose that a number \(a\) can be written in standard factored form
$$a=p_1^{e_1}p_2^{e_2}\cdot\cdot\cdotp_k^{e_k}$$
where
\(k\) is a positive integer.
\(p_1,p_2, ...,p_k\) are prime numbers with \(p_1 \lt p_2 \lt ... \lt p_k\).
\(e_1,e_2, ...,e_k\) are positive integers.
What is the standard factored form for \(a^3\)?
Find the least positive integer such that
$$2^4\cdot3^5\cdot7\cdot11^2\cdot k$$
is a perfect cube. Write the resulting product as a perfect cube.
Evan Brooks CP03: How many zeros are at the end of the number \(35^{113}\cdot 48^{23}\)? Explain how you can answer this question without actually computing the number. (Hint: \(10=2\cdot5\).)
Michael Cooney CP03: Prove that for any nonnegative integer \(n\), if the sum of the digits of \(n\) is divisible by \(9\), then \(n\) is divisible by \(9\). (Hint: Study Exercise 4.3#47 for a concrete example, and then generalize that example.)
Quiz Q04 on Wed Sep 28, Covers Epp 4th Edition Sections 4.2 and 4.3
Fri Sep 30 is Fall Break: No Class. Stay home and study math!!
Week 7 (Mon Oct 3 through Fri Oct 7)
Mon Oct 3:
Section to Discuss: Epp 4th Edition Section 4.4 Direct Proof and Counterexample V: Division into Cases and the Quotient Remainder Theorem:
Exercises from Epp 4th Edition Section 4.4 Direct Proof and Counterexample V:: # 1,3,5,7,10,13,14,17,20,23,25,27,28a,29,9036,37,38,39
Video: Video for Epp 5th Edition Section 4.5 = Topics from Epp 4th Edition Section 4.4 (link to video) (Link to Notes)
Find \(50\text{ div }7\) and \(50\text{ mod }7\). Show the corresponding \(n=dq+r\) equation.
Find \(-50\text{ div }7\) and \(-50\text{ mod }7\). Show the corresponding \(n=dq+r\) equation.
Find \(56\text{ div }7\) and \(56\text{ mod }7\). Show the corresponding \(n=dq+r\) equation.
Lucas Fernandes CP3: (similar to Epp 4th Edition Section 4.4 Exercise #20)
If \(c\) is an integer such that \(c \text{ mod } 13 = 5\), then what is \(6c \text{ mod } 13\)?
In other words, if division of \(c\) by 13 gives a remainder of \(5\), what is the remainder when \(6c\) is divided by \(13\)? Explain using \(n=dq+r\) equations.
Luke Haskell CP3: (similar to Epp 4th Edition Section 4.4 Exercise #23)
Prove that for all integers \(a\) and \(b\), if \(a \text{ mod } 7 = 5\) and \(b \text{ mod } 7 = 6\), then \(ab \text{ mod } 7 = 2\).
Hint: Prove using \(n=dq+r\) equations.
Wed Oct 5:
Section to Discuss: Epp 4th Edition Section 4.4 Direct Proof and Counterexample V: Division into Cases and the Quotient Remainder Theorem:
Exercises from Epp 4th Edition Section 4.4 Direct Proof and Counterexample V:: # 1,3,5,7,10,13,14,17,20,23,25,27,28a,29,9036,37,38,39
Video: Video for Epp 5th Edition Section 4.5 = Topics from Epp 4th Edition Section 4.4 (link to video) (Link to Notes)
Class Presentations for Wed Oct 5
Ethan Levingston CP3: (similar to Epp 4th Edition Section 4.4 Exercise #29) Suppose that \(n\) is an integer.
What does the Quotient Remainder Theorem with \(d=2\) tell us about \(n\)?
What does the Quotient Remainder Theorem with \(d=3\) tell us about \(n\)?
Use the Quotient Remainder Theorem with \(d=3\) to prove that the cube of any integer has the form \(3k\) or \(3k+1\) or \(3k+2\) for some integer \(k\).
Jennifer Lewis CP3: (similar to Epp 4th Edition Section 4.4 Exercise #30) Recall that two consecutive integers can always be written in the form \(n(n+1)\), where \(n\) is an integer.
What does the Quotient Remainder Theorem with \(d=3\) tell us about \(n\)?
Your result of (a) should give you three possible cases for \(n\). What are the resulting values of \(n(n+1)\) in those three cases?
Use the Quotient Remainder Theorem with \(d=3\) to prove that the product of any two consecutive integers has the form \(3k\) or \(3k+2\) for some integer \(k\).
Quiz Q05 on Wed Oct 5 over \(n=dq+r\) and MOD and DIV from Epp 4th Edition Section 4.4.
Fri Oct 7:
Section to Discuss: Epp 4th Edition Section 4.6: Indirect Argument: Contraposition and Contraposition
Exercises:
Exercises about rational and irrational numbers: Epp 4th Edition Section 4.6 # 2 and these Three Extra Questions:
Suppose that \( q=a/b \) is a rational number. What does that tell you about \(a\) and \(b\)?
Suppose that \( q=a/b \) is a rational number and \(q=0\). What does that tell you about \(a\) and \(b\)?
Suppose that \( q=a/b \) is a rational number and \(q \neq 0\). What does that tell you about \(a\) and \(b\)?
Exercises to be proven directly, not using contradiction and not proving the contrapositive: Epp 4th Edition Section 4.6 # 4,5,6,7,17
Exercises to be proven indirectly, by proving the contrapositive: Epp 4th Edition Section 4.6 # 10,12,14,15,19,21,22,24,25,26,27,28
Exercises to be proven indirectly by contradiction: Epp 4th Edition Section 4.6 # 16
Remark: Observe that out of all of the exercises that I assign in this section, only one needs to be proven by contradiction!
Video: Video for Epp 5th Edition Section 4.7 = Topics from Epp 4th Edition Section 4.6 (link to video)
Notes: Notes from Video for Epp 5th Edition Section 4.7 (Link to Notes)
Handouts: Handout on Overuse of the Method of Contradiction (Link to Handout)
Class Presentations for Fri Oct 7
Daniel Lipec CP3: Suppose that \(k\) is an integer.
What does the Quotient Remainder Theorem (QRT) with \(d=3\) tell you about \(k\)?
What does the remainder \(r\) have to be if the unknown \(k\) is going to be divisible by \(3\)?
Suppose that it is known that \(k=3m+2\) for some integer \(m\). Is \(k\) divisible by \(3\)?
Bradey Lounsbury CP3: Let \(S\) be the statement
$$\forall m\in \mathbb{Z} \left( \exists n \in \mathbb{Z} \left( n \gt n \right) \right)$$
Prove \(S\).
Find the negation of \(S\).
Is the negation of \(S\) true or false? Explain.
Bryce Nicholson CP3: Let \(S\) be the statement
$$\forall x \in \mathbb{R} \left( \text{ If }\sqrt{x} \in \mathbb{Q} \text{ then }x\in \mathbb{Q} \right)$$
Prove \(S\).
Find the contrapositive of \(S\).
Is the contrapositive of \(S\) true or false? Explain.
Week 8 (Mon Oct 10 through Fri Oct 14)
Bonus Quiz BQ1 due at the start of class on Mon Oct 10. (Link to Bonus Quiz) If you do not have a printout of this quiz, then you must find a way to print one. I will not accept hand-written solutions that are not on a printed quiz.
Mon Oct 10:
Section to Discuss: Epp 4th Edition Section 4.6: Indirect Argument: Contraposition and Contraposition
Exercises:
Exercises about rational and irrational numbers: Epp 4th Edition Section 4.6 # 2 and these Three Extra Questions:
Suppose that \( q=a/b \) is a rational number. What does that tell you about \(a\) and \(b\)?
Suppose that \( q=a/b \) is a rational number and \(q=0\). What does that tell you about \(a\) and \(b\)?
Suppose that \( q=a/b \) is a rational number and \(q \neq 0\). What does that tell you about \(a\) and \(b\)?
Exercises to be proven directly, not using contradiction and not proving the contrapositive: Epp 4th Edition Section 4.6 # 4,5,6,7,17
Exercises to be proven indirectly, by proving the contrapositive: Epp 4th Edition Section 4.6 # 10,12,14,15,19,21,22,24,25,26,27,28
Exercises to be proven indirectly by contradiction: Epp 4th Edition Section 4.6 # 16
Remark: Observe that out of all of the exercises that I assign in this section, only one needs to be proven by contradiction!
Video: Video for Epp 5th Edition Section 4.7 = Topics from Epp 4th Edition Section 4.6 (link to video)
Notes: Notes from Video for Epp 5th Edition Section 4.7 (Link to Notes)
Handout: Handout on Overuse of the Method of Contradiction (Link to Handout)
Class Presentations for Mon Oct 10
Brittany Poss CP3: The goal is to prove the following Statement A:
For all \(n\in \mathbb{Z}\), if \(n^2\) is odd then \(n\) is odd.
Write the contrapositive of Statement A.
Prove the contrapositive.
Clair Schmidt CP3: The goal is to prove the following Statement B:
For all real numbers \(a,b,r\) such that \(a,b \in \mathbb{Q}\) and \(b\neq0\), if \(r\) is irrational, then \(a+br\) is irrational.
Write the contrapositive of Statement B.
Prove the contrapositive.
Jake Schneider CP3: The goal is to prove the following Statement C:
$$\forall a,b,c \in \mathbb{Z} \left( \text{If } a \nmid bc \text{ then } a \nmid b \right)$$
(Note that the symbol \( \nmid\) means does not divide.)
Write the contrapositive of Statement C.
Prove the contrapositive.
Wed Oct 12:
Section to Discuss: Epp 4th Edition Section 4.7: Indirect Argument: Two Classical Theorems
Video: There is no video prepared for this section of the book.
Handouts: Handout on Overuse of the Method of Contradiction (Link to Handout)
Class Presentations for Wed Oct 12
Nicole Strang CP3: Find the negation of Statement S:
$$\text{Statement }S: \forall n \in \mathbb{Z}, p\in Primes \left(\text{If }p \mid n\text{ then }p \nmid (n+1) \right)$$
(Note that the symbol \( \mid\) means divides and the symbol \( \nmid\) means does not divide.)
Take-HomeQuiz Q06: Handed out on Wed Oct 12, Due Fri Oct 14, covering Epp 4th Edition Section 4.6, based on one of the exercises in the list
4.6#10,12,15,19,21,22,24,25,26,27,28.
(These problems have various instructions in the book. For many of them, the book says to prove the statement using contradiction. But these problems are taken from your suggested exercises for Section 4.6, and my instructions for all of them are to prove the contrapositive, and not use contradiction.)
Fri Oct 14:
Sections to Discuss:
Epp 4th Edition Section 4.7: Indirect Argument: Two Classical Theorems
Video: There is no video prepared for this section of the book.
Class Presentations for Fri Oct 14
Rashid Al Busa'idi CP3:
Find the negation of this statement:
$$ \forall p\in B \left(\forall x,y,z \in \mathbb{Z}\left(x^p+y^p\neq z^p \right) \right)$$
Find the negation of this statement:
$$ \forall n\in C \left(\forall x,y,z \in \mathbb{Z}\left(x^n+y^n\neq z^n \right) \right)$$
Find the contrapositive of this statement:
$$\text{If }\left( \forall p\in B \left(\forall x,y,z \in \mathbb{Z}\left(x^p+y^p\neq z^p \right) \right) \right)\text{ then }
\left( \forall n\in C \left(\forall x,y,z \in \mathbb{Z}\left(x^n+y^n\neq z^n \right) \right) \right)$$
Gretchen Angst CP4: (based on Epp 4th Edition Exercise 4.8#15)
The goal is to find the greatest common divisor of \(832\) and \(10933\) two ways
Show how to use Wolfram Alpha. (Project onto the screen.)
Show the steps using the Euclidean algorithm (see Epp 4th Edition pages 222-224)
Evan Brooks CP4: (related to Epp 4th Edition Exercise 4.8#15)
The goal is to find the greatest common divisor of \(832\) and \(10933\) in a different way, using the prime factorizations.
Show the prime factorizations of \(832\) and \(10933\)
Using those prime factorizations to explain what the greatest common divisor of those two numbers is.
Michael Cooney CP4: (related to Epp 4th Edition Exercise 4.8#25)
The goal is to find the least common multiple of \(832 \)and \(10933\) using the prime factorizations.
Show the prime factorizations of \(832\) and \(10933\)
Using those prime factorizations to explain what the least common multiple of those two numbers is.
Week 9 (Mon Oct 17 through Fri Oct 21)
Mon Oct 17:
Section to Discuss: Epp 4th Edition Section 4.8: The Euclidean Algorithm
Video: There is no video prepared for this section of the book.
Class Presentations for Mon Oct 17
Julie Fausnaugh CP4: (Your topic will be part of Monday’s discussion of greatest common divisor and least common multiple, but your topic is background, not related to anything discussed in the book.)
Prove that if \(j\) and \(k\) are any two integers, then \(max\{j,k\}+min\{j,k\}=j+k\).
(Hint: Notice that there is an OR statement that can be articulated:
$$j \lt k \ \text{ OR } \ j = k \ \text{ OR } \ j \gt k$$
Exploit that to set up a proof by cases.)
The next two presentations will be part of the review portion of the class meeting, reviewing concepts from Epp 4th Edition Section 4.4.
To review the Quotient Remainder Theorem
Read Epp 4th Edition Section 4.4 Direct Proof and Counterexample V: Division into Cases and the Quotient Remainder Theorem.
Watch the Video for Epp 5th Edition Section 4.5 = Topics from Epp 4th Edition Section 4.4 (link to video)
Lucas Fernandes CP4: (See note above about reviewing the Quotient Remainder Theorem.) Let \(n\) be an integer. What does the Quotient Remainder Theorem with \(d=4\) say about \(n\)?
Luke Haskell CP4: (See note above about reviewing the Quotient Remainder Theorem.) Solve Epp 4th Edition exercise 4.4#36: Prove that the product of any four consecutive integers is diviible by 8. (Hint: Let your four consecutive integers be \(n,n+1,n+2,n+3\). Then use the Quotient Remainder Theorem with \(d=4\) to get four possibilities for \(n\).
Exam X2 on Wed Oct 19 Covering Chapter 4
The exam is the full class period.
No calculators, books, or notes
The Exam is typeset on 6 pages, printed on front & back of 3 sheets of paper.
The exam is six questions, 30 points each
(Easy) Given a repeating decimal, write it as a ratio of integers (read 4th Edition Section 4.2, watch Video for 5th Edition Section 4.3)
(Easy) Compute the Unique prime factorizations, GCD & LCM of two numbers (read 4th Edition Section 4.3, watch Video for 5th Edition Section 4.4)(read 4th Edition Section 4.8, which has no video)
(Moderate) Disprove a statement about composite & prime numbers (read 4th Edition Section 4.1, watch Video for 5th Edition Section 4.1,4.2)
(Moderate) Prove a statement about Divisibility (read 4th Edition Section 4.3, watch Video for 5th Edition Section 4.4)
(Moderate) A proof involving the Quotient-Remainder Theorem (read 4th Edition Section 4.4, watch Video for 5th Edition Section 4.5)
(Moderate) Prove a universal conditional statement by proving its contrapositive (read 4th Edition Section 4.6, watch Video for 5th Edition Section
Fri Oct 21:
Section to Discuss: Epp 4th Edition Section 5.1 Sequences
Expanded form often looks more intimidating than product notation, but it sometimes makes things more complicated.
Consider this telescoping product, presented in expanded form:
Suppose that the goal is use the Method of Proof by Induction to prove the following statement:
$$\forall n\in \mathbb{Z},n\geq1 \left(1+6+11+16+\dotsm +(5n-4)=\frac{n(5n-3)}{2}\right)$$
Your job is to do the preliminary work:
What is the predicate, \(P(n)\)?
What is the number playing the role of \(a\)?
Write the expression for \(P(a)\).
Write the expression for \(P(k)\).
Write the expression for \(P(k+1)\).
Note: Don’t do the proof! Just do the preliminary work.
Suppose that the goal is use the Method of Proof by Induction to prove the following statement:
$$\forall n\in \mathbb{Z},n\geq1 \left(1^3+2^3+3^3+\dotsm+n^3=\left[\frac{n(n+1)}{2}\right]^2\right)$$
Your job is to do the preliminary work:
What is the predicate, \(P(n)\)?
What is the number playing the role of \(a\)?
Write the expression for \(P(a)\).
Write the expression for \(P(k)\).
Write the expression for \(P(k+1)\).
Note: Don’t do the proof! Just do the preliminary work.
Week 11 (Mon Oct 31 through Fri Nov 4)
Mon Oct 31
Leftovers from Section 5.2 Mathematical Induction I
Epp 4th Edition Proposition 5.2.1 (on page 247) For all integers \(n\geq8\), \(n\) cents can be obtained using \(3\) cent and \(5\) cent coins. (A detailed proof of the proposition provided in book.) On one hand, this is a simpler example because it does not involve complicated formulas. On the other hand is a difficult example because it involves both induction and proof by cases.
Homework problem Epp 4th Edition 5.2#1: Use mathematical induction (and the proof of Proposition 5.2.1 as a model) to show that any amount of money of at least \(14\) cents can be made up using\( 3 cent and \(8\) cent coins. (A detailed solution provided in the back of the book.)
Homework problem Epp 4th Edition 5.2#2: Use mathematical induction to show that any postage of at least \(1\)2 cents can be obtained using \(3\) cent and \(7\) cent stamps.
I won’t discuss this kind of problem in class: there is excellent coverage in the book, and I want you to learn this by reading the book. I will put a problem like this on the exam. So
Study the proposition.
Work Problem 5.2#1, using the proof of the proposition as your guide. Compare your solution to the book’s solution.
Work Problem 5.2#2, using the proof of the proposition and your own proof of 5.2#1 as a guide.
In Epp 4th Edition Section 1.3 and Section 8.1, and in class on Wed Nov 9, you saw that the words \(S\) is a relation on the set of real numbers means simply that \(S\) is a subset of \(\mathbb{R}\times\mathbb{R}\). That is, \(S\) is simply some set of ordered pairs of real numbers. And you saw that the symbol \( _xS_y\) is is spoken \(x\) is related to \(y\), and it means that the ordered pair \((x,y)\) is an element of the set \(S\). To define an actual relation, it must be specified what it actually means to say \( _xS_y\) That is, it must be specified what it actually means to say \(x\) is related to \(y\).
For example one could say that \( _xS_y\) means \(y=5x+3\). Then observe that the ordered pair \((x,y)=(1,8)\) is an element of \(S\), because the equation \(8 = 5(1) +3\) is true. We would say that \(1\) is related to \(8\). This could be abbreviated \( _1S_8\). But the ordered pair \((x,y)=(8,1)\) is not an element of \(S\), because the equation \(1 = 5(8) +3\) is not true. We would say that \(1\) is not related to \(8\).
Relations on the set of real numbers can be visualized, because they are subsets of the cartesian plane \(\mathbb{R}\times\mathbb{R}\). A graph of a relation \(S\) on the set of real numbers is simply a picture of all of the elements of the set \(S\). In the case of the relation \(S\) introduced above, the graph of \(S\) is just a picture of all of the ordered pairs \((x,y)\) that satisfy the equation \(y=5x+3\). In other words, the graph of \(S\) is just a line with slope \(m=5\) and \(y\) intercept at \((x,y)=(0,1)\).
Eight students will each be given descriptions of relations on the set of real numbers. That means, they will be given a specification of what it actually means to say x is related to y. Their job is to draw a graph of the relation. ( Graph the relation on the chalkboard at the start of class.)
Nikki Strang CP4: \( _xS_y\) means \(y=x^2\).
Rashid Al Busa’idi CP4: \( _xS_y\) means \(x=y^2\).
Gretchen Angst CP5: \( _xS_y\) means \(x^2=y^2\).
Evan Brooks CP5: \( _xS_y\) means \(x \lt y\).
Michael Cooney CP5: \( _xS_y\) means \(x \leq y\).
Julie Fausnaugh CP5: \( _xS_y\) means \(xy=0\).
Luke Haskell CP5: \( _xS_y\) means \(xy\neq0\).
Ethan Levingston CP5: \( _xS_y\) means \(x=(y+\text{ some multiple of }10)\).
Then we’ll discuss Properties that Relations on a Set May or May Not Have: Reflexivity, Symmetry, Transitivity.
Video: A video has not been prepared for Section 8.4
Class Presentations
The presentations for today deal with the relation \(F\) that is the congruence modulo \(5\) relation on the set \(\mathbb{Z}\), defined as follows:
For \(m,n \in \mathbb{Z}\), the symbol \(\ _mF_n\) means \(5|(m-n)\).
The presentations are taken from Suggested Exercise Epp 4th Edition 8.2#13. To study for these presentations, Study Epp 4th Edition Example 8.2.4 on page 455-456.
Nicole Strang CP5: Prove that \(F\) is reflexive.
Rashid Al Busa'idi CP5: Prove that \(F\) is symmetric.
Video: A video has not been prepared for Section 8.4
Meeting Part 1: Properties of Congruence Modulo \(n\)
Last Monday, Nov 28, we discussed the relation \(F\) that is the congruence modulo \(5\) relation on the set \(\mathbb{Z}\), defined as follows:
For \(m,n \in \mathbb{Z}\), the symbol \(\ _mF_n\) means \(5|(m-n)\).
On that Monday, we saw (in Class Presentations) that this relation is reflexive, symmetric, and transitive. Because the relation has all three of those properties, we say that it is an equivalence relation.
In Epp 4th Edition Section 8.3, you learned about equivalence classes for an equivalence relation.
Class Presentation: Roman Simkins CP4: Describe the distinct equivalence classes of relation \(F\) introduced above. (Hint: This presentation is similar to Suggested Exercise Epp 4th Edition 8.3#21. To study for this presentation, read about equivalence classes in Epp 4th Edition Section 8.3. In particular, study Example 8.3.10 on pages 471-472.)
Mark B will talk a bit about properties of equivalence classes (Concepts from Section 8.3).
Mark B will talk a bit about modular equivalence, and various notation related to it.
Class Presentation: Grace Smith CP4: Which of these are true and which are false? Explain. (Hint: The notation \(m \equiv n \mod d\) is Defined on Epp 4th Edition p.473. The next presentation is about that notation. It is similar to Suggested Exercise Epp 4th Edition 8.3#15. To study for this presentation, Study Epp 4th Edition Example 8.3.11 on p. 473.)(Justify your answers using \(n=dq+r\) equations.)
\(-3 \equiv 3 \ (\text{mod }5)\)
\(-3 \equiv -13 \ (\text{mod }5)\)
\(42 \equiv 14 \ (\text{mod }7)\)
\(42 \equiv 7 \ (\text{mod }14)\)
Mark B will brieflly discuss the terminology of residues.
Mark B will briefly discuss Theorem 8.4.2 Congruence Modulo \(n\) Is an Equivalence Relation.
Meeting Part 2: Modular Arithmetic
Mark B will briefly discuss Theorem 8.4.3 and Corollary 8.4.4 about Modular Arithmetic.
Six Class Presentations Presenting a Solution to Epp 4th Edition Section 8.4 Exercise #8 (Hint: This exercise is just like Suggested Exercise #7 and Example 8.4.2. (Justify your answers using \(n=dq+r\) equations.))
Lucas Fernandes CP5: Verify that \(45 \equiv 3 \ (\text{mod }6)\) and that \(104 \equiv 2 \ (\text{mod }6)\).
Jennifer LewisCP5: Verify that \((45+104) \equiv (3+2) \ (\text{mod }6)\).
Daniel Lipec CP5: Verify that \((45 \cdot 104) \equiv (3 \cdot 2) \ (\text{mod }6)\).
Bryce Nicholson CP5: (Hint: This exercise is just like Suggested Exercise Epp 4th Edition Section 8.4 #14. Use the technique of Epp 4th Edition Section 8.4 Example 8.4.4.) (Justify your answers using \(n=dq+r\) equations.)
Find the following quantities:
\(13 \ (\text{mod }54)\)
\(13^2 \ (\text{mod }54)\)
\(13^4 \ (\text{mod }54)\)
\(13^8 \ (\text{mod }54)\)
\(13^{16} \ (\text{mod }54)\)
Mark B will use Bryce’s results to find \(13^{22} \ (\text{mod }54)\). (This problem is similar to Suggested Exercise Epp 4th Edition Section 8.4 #15, using the technique illustrated in Example 8.4.5.)
Meeting Part 3 (On Monday, if we get to it. Otherwise on Wednesday): Extending the Euclidean Algorithm
Mark B will briefly discuss Theorem 8.4.5.
Group Activity: Expressing a Greatest Common Divisor as a Linear Combination: Mimicking the steps of Example 8.4.7, Show that \(154\) and \(135\) are relatively prime, and find a linear combination of \(154\) and \(135\) that equals \(1\).
Group Activity 1: Expressing a Greatest Common Divisor as a Linear Combination: Mimicking the steps of Example 8.4.6,
Find \(\text{gcd}(105,385)\)
Find a linear combination of \(105\) and \(385\) that equals \(\text{gcd}(105,385)\).
Group Activity 2: Expressing a Greatest Common Divisor as a Linear Combination: Mimicking the steps of Example 8.4.7,
Show that \(154\) and \(135\) are relatively prime
Find a linear combination of \(154\) and \(135\) that equals \(1\).
Find the multiplicative inverse of \(154\) modulo \(135\).
Find the multiplicative inverse of \(135\) modulo \(154\).
Wed Nov 30
Sections to Discuss:
Epp 4th Edition Section 8.4 Modular Arithmetic with Applications to Cryptography
Video: A video has not been prepared for Section 8.4
Meeting Part 1: Extending the Euclidean Algorithm
Mark B will briefly discuss Lemma 4.8.2.
If \(a\) and \(b\) are any integers not both zero, andif \(q\) and \(r\) are any integers such that
$$a=bq+r$$
then
$$\text{gcd}(a,b)=\text{gcd}(b,r)$$
Mark B will briefly discuss the terminology of linear combination of integers
Mark B will briefly discuss Theorem 8.4.5.
For all integers \(a\) and \(b\), not both zero, if \(d=\text{gcd}(a,b)\), then there exist integers \(s\) and \(t\) such that \(as+bt=d\). That is, the greatest common divisor of \(a\) and \(b\) can be written as a linear combination of \(a\) and \(b\).
Clair Schmidt Presentation CP5: Expressing a Greatest Common Divisor as a Linear Combination: Mimicking the steps of Example 8.4.6,
Find \(\text{gcd}(105,385)\)
Find a linear combination of \(105\) and \(385\) that equals \(\text{gcd}(105,385)\).
Mark B will briefly discuss relatively prime integers and Corollary 8.4.6 and Corollary 8.4.7.
Brittany Poss Presentation CP5: Expressing 1 as a linear combination of relatively prime integers and Finding a Multiplicative Inverse Modulo \(n\): Mimicking the steps of Example 8.4.7 and Example 8.4.8
Show that \(77\) and \(15\) are relatively prime
Find a linear combination of \(77\) and \(15\) that equals \(1\).
Find a multiplicative inverse of \(77\) modulo \(15\).
Find a positive multiplicative inverse of \(77\) modulo \(15\).
Find a multiplicative inverse of \(15\) modulo \(77\).
Meeting Part 2: Quiz Q10 covering Epp 4th Edition Section 8.4 (Some concepts in 8.4 also appeared in 8.2 and 8.3)
Quiz Q10 on Wed Nov 30 Covers Section 8.4
Fri Dec 2
Sections to Discuss:
Epp 4th Edition Section 8.4 Modular Arithmetic with Applications to Cryptography
Video: A video has not been prepared for Section 8.4
Intro to RSA Cryptography
Roman Simkins Class Presentation CP5: Finding a Multiplicative Inverse Modulo \(n\): Observe that \(9\) and \(44\) are relatively prime. Mimicking the steps of Example 8.4.7 and 8.4.8, find a positive number that is a multiplicative inverse of \(9\), modulo 44.
Jake Schneider Class Presentation CP5: Compute \(4^9 \ (\text{mod }69)\). Explain your result using an \(n=dq+r\) equation.
Grace Smith Class Presentation CP5: Compute \(13^5 \ (\text{mod }69)\). Explain your result using an \(n=dq+r\) equation.
Students: Break into two groups and do the RSA Activity.
Week 16 (Mon Dec 7 through Fri Dec 11)
Final Exam on Mon Dec 5 from 10:10am - 12:10pm in Morton 218
The Exam will be seven problems, 30 points each.
A problem about negating a statement that may include IF-THEN, AND, OR as well as Quantifiers (Chapter 3 concepts)
A problem about the converse, contrapositive, inverse and negation of a universal conditional statement. (Chapter 3 concepts)
Choose one (Chapter 4 concepts):
Prove or disprove a statement about even and odd numbers
Prove or disprove a statement about prime and composite numbers
Prove or disprove a statement about divisibility
Prove a statement by proving its contrapositive. (Chapter 4 concepts)
Prove a statement by induction. (Chapter 5.2 or 5.3 concepts)
One of these five problems: 8.4 # 5, 6, 9, 10, 11 (The description for this problem changed on Saturday morning. I want to be sure that you spend a bit of time reviewing the basic properties of modular congruence that are the core of modular arithmetic. Note that 9,11 are the proofs of Theorem 8.4.3 Parts 1,2,4. The proof of Theorem 8.4.3 Part 2 is done in the book.)
Given integers \(a\) and \(b\), find \(\text{gcd}(a,b)\) and find a linear combination of \(a\) and \(b\) that equals \(\text{gcd}(a,b)\). (Chapter 8.4 concepts)
I will make the study guide more precise once I have the exam written. Meanwhile, your study approach should be the following:
Top Priority: Study graded Quiz & Exam problems (on the topics above) that you got right and make sure that you can still do those problems. That is the low-hanging fruit: the stuff that you once knew well. Those skills should come back to you the quickest.
Second Priority: Study graded Quiz & Exam problems (on the topics above) that you got wrong. See if you can figure them out.
Third Priority: Review Suggested Homework Problems (on the topics above) that you have done before. (Check to see if there are answers in the back of the book, or similar examples in the book.)
Fourth Priority: Do Suggested Homework Problems (on the topics above) that you have not done before. (Check to see if there are answers in the back of the book, or similar examples in the book.)
Lower Priority: Sleep, eat, bathe, go to work at your job, study for your other classes, feed your pets.
Grading for MATH 3070/5070 Section 100
2022 - 2023 Fall Semester
During the course, you will accumulate a Points Total of up to 1000 possible points.
Presentations: 5 Presentations (during Meetings) @ 10 points each = 50 points possible
Quizzes: 10 quizzes @ 20 points each = 200 points possible
Exams: 3 Exams @ 180 points each for a total of 540 points possible
Final Exam: 210 points possible
At the end of the semester, your Points Total will be divided by \(1000\) to get a percentage, and then converted into your Course Letter Grade using the 85%, 70%, 55%, 40% Grading Scale described below.
The 85%, 70%, 55%, 40% Grading Scale is used on all graded items in this course, and is used in computing your Course Letter Grade.
A grade of A, A- means that you mastered all concepts, with no significant gaps.
If \(90\% \leq score \), then letter grade is A.
If \(85\% \leq score < 90\%\), then letter grade is A-.
A grade of B+, B, B- means that you mastered all essential concepts and many advanced concepts, but have some significant gap.
If \(80\% \leq score < 85\%\), then letter grade is B+.
If \(75\% \leq score < 80\% \), then letter grade is B.
If \(70\% \leq score < 75\%\), then letter grade is B-.
A grade of C+, C, C- means that you mastered most essential concepts and some advanced concepts, but have many significant gaps.
If \(65\% \leq score < 70\%\), then letter grade is C+.
If \(60\% \leq score < 65\%\), then letter grade is C.
If \(55\% \leq score < 60\%\), then letter grade is C-.
A grade of D+, D, D- means that you mastered some essential concepts.
If \(50\% \leq score < 55\%\), then letter grade is D+.
If \(45\% \leq score < 50\% \), then letter grade is D.
If \(40\% \leq score < 45\%\), then letter grade is D-.
A grade of F means that you did not master essential concepts.
If \(0\% \leq score < 40\%\), then letter grade is F.
Keeping Track of Your Current Grade
During the semester, you can keep track of your scores on all the Graded Items: Class Presentations, Quizzes, Exam, Final Exam. (You can also find scores for all those items in the Blackboard Gradebook. Of course, you can also find your Quiz and Exam scores by just looking at your graded Quizzes and Exams.) Using this Grade Calculation Worksheet, can determine your Current Grade throughout the semester.
Attendance: Attendance is recorded but is not part of your course grade
Exercises: There is a list of Suggested Exercises on this web page. To succeed in the course, you will need to do lots of them. But these are not graded and are not part of your course grade.
Learning Objectives:
Learning Objectives for the course will be posted here on Tue Aug 23.