EECS 203: Discrete Mathematics
Fall 2024
Homework 2
Legal assumptions
• You may assume any of the following without proof: the laws of algebra are valid, the sum or difference of two integers is an integer, the product of two integers is an integer.
• Additionally, you may use any facts about modular arithmetic/algebra without jus-tification, such as the rules of modular addition and multiplication. This includes facts about algebra on even and odd numbers, such as even + dd = odd, even · dd = even, etc. (since these are equivalent to addition and multiplication mod 2).
Definitions and Notation
• An integer x is divisible by d if there exists an integer k with x = dk.
• An integer x is rational if there exist integers a, b with x = a/b. Otherwise, it is irrational.
• An integer x is prime if x ≥ 2, and there do not exist integers j ≥ 2, k ≥ 2 with x = jk.
• An integer x is even if there is an integer k with x = 2k, or odd if there is an integer k with x = 2k + 1. If convenient, you may also use that x is even if x ≡ 0 (mod 2), or odd if x ≡ 1 (mod 2).
Mechanical Problems
1. Even Stevens [14 points]
Consider the proposition: for all integers x, y, if 3xy + 4x + y is odd then x is odd or y is odd. Give three separate proofs, using:
(a) a proof by contrapositive
(b) a proof by contradiction
(c) a proof by cases on whether x is even or odd.
2. Rooting For You [14 points]
Prove that for all odd integers a, b, c, the equation ax2 + bx + c = 0 does not have any solutions where x is an integer.
3. Bad Id34 [14 points]
(a) Prove that √3 is irrational.
(b) Note that √4 = 2, which is rational. What step in your proof would go wrong if you used the same proof strategy to show that √4 is irrational? Cite a specific step or claim from your previous answer, and explain in a sentence or two why it is incorrect for √4.
4. It’s A Very Very ... Mod World [12 points]
Calculate 7203 mod 5. Show your work. Your solution should not contain any numbers greater than 50 except for exponents.
Bad Proofs
Each of the following propositions may or may not be true, but we have given an incorrect “proof” that attempts to show that it is true. Identify the specific logical error made in each proof by citing a sentence, equation, step, or missing part of the proof, and briefly explain why it is wrong.
5. Irrational Inaccuracy [8 points]
Proposition. √6 is irrational.
Incorrect Proof. We have √6 = √2 · 3 = √2 ·
√3. We proved in class that √2 is irrational, and we proved previously in this homework that √3 is irrational. So √6 is the product of two irrational numbers, so it is irrational.
6. Parity Ploy [8 points]
Proposition. For all integers x and y, if one of the variables is even and the other is odd, then their sum is even.
Proof. We use a proof by contrapositive. Switching the order of the if-then and negating each side, we get:
“For all integers x and y, if their sum is odd, then one of the variables is odd or the other is even.”
Letting x and y be any integers whose sum is odd, we must either have that x is even and y is odd, or that x is odd and y is even. In either case it holds that one of the variables is odd or the other is even, so the proposition is proved.
Discovery Problems
7. Lucky Seven [15 points]
(a) Prove that any positive integer n is divisible by 9 if and only if the sum of its digits is divisible by 9.
(b) For which integers 2 ≤ d ≤ 7 is it true that a number is divisible by d if and only if the sum of its base-7 digits is divisible by d? Give a complete list of these integers, and explain how you might change your proof from the previous part to show this property for the integers in your list.
For full credit you must include all integers with this property in your list, but you do not need to prove that your list is indeed complete.
8. Prime Pairs [15 points]
The twin prime conjecture is a famous unsolved problem, which asks for a proof or dis-proof that there are infinitely many pairs of prime numbers whose difference is exactly 2 (for example: (3, 5),(5, 7),(11, 13),(17, 19)). We will investigate two related (but solved) problems:
(a) Prove or disprove: there are infinitely many pairs of prime numbers whose difference is exactly 3.
(b) Prove or disprove: there are infinitely many pairs of prime numbers whose difference is a nonzero multiple of 3.
Note: We proved in lecture that there are infinitely many prime numbers; you can use this without re-proving it. If you’re having trouble, try listing some small primes and noting which pairs have a difference that is a multiple of 3. Do you notice a pattern?