Problem Set 7—Proofs in Cases

Purpose

This problem set develops your ability to write proofs that use multiple cases, and begins to develop your ability to reason with congruences. It also reinforces habits of formal writing in proofs.

Background

This problem set is based on material in sections 3.4 and 3.5 of our textbook. We discussed or will discuss this material in class on February 22 and 24.

Activity

Do the following exercises. All proofs should be word-processed (i.e., not hand-written) and should follow the guidelines in Sundstrom’s text, particularly the new guideline of clearly identifying each case in a multi-case proof.

Exercise 1

Exercise 5a in section 3.4 of Sundstrom’s text (prove that for all integers a, b, and d with d ≠ 0, if d divides a or d divides b, then d divides ab).

Exercise 2

Exercise 6b in section 3.4 of Sundstrom’s text (determine whether it is true or false that for all integers m and n, 4 divides m² - n² if and only if m and n are both even or m and n are both odd; see book for additional requirements if the proposition is false).

Exercise 3

Exercise 7 in section 3.4 of Sundstrom’s text (determine whether it is true or false that for all integers n, if n is odd then 8 | (n²-1); prove the proposition or provide a counterexample, according to whether you think it is true or false). The notation a | b means “a divides b,” i.e., b = ka for some integer k.

Exercise 4

Part A

Extend Sundstrom’s Proposition 3.33 by proving that if a is an integer and a ≡ 0 (mod 5) then a² ≡ 0 (mod 5).

Part B

Exercise 11a in section 3.5 of Sundstrom’s text (prove that 5,344,580,232,468,953,153 is not a perfect square; see textbook for additional information).

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.