DOC PREVIEW
UMD CMSC 250 - Homework 5 Answers

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC250, Spring 2004 Homework 5 AnswersDue Wednesday, March 3 at the beginning of your discussion section.You must write the solutions to the problems single-sided on your own lined paper,with all sheets stapled together, and with all answers written in sequential order oryou will lose points.Prove each of the following statements true or false. Remember, a counterexample may onlybe used to prove that a “for all” statement is false, and all counterexamples must include specificvalues and enough algebra/justification to show that they are truly counterexamples.1. For all integers a, b, and c, if a + b = c and a | b, then a | c.Answer: TRUE.Let a, b, and c be arbitrary integers.Assume a + b = c and a | b.Since a | b, ∃k ∈ Z ak = b by definition of divides.ak + a = b + a by adding a to both sides.a(k + 1) = c by algebra and substitution.k + 1 ∈ Z by closure of the integers under addition.a | c by definition of divides.∀a, b, c ∈ Z (a + b = c) ∧ (a | b) → (a | c) by closing of conditional world and generalizingfrom the generic particular.2. ∀a, b, c ∈ Z [(a | c) ∧ (b | c)] → [(a | b) ∨ (b | a)]Answer: FALSE.Counterexample: Let a = 2, b = 3, and c = 6.Then a | c and b | c since 2 | 6 and 3 | 6. However, 2 - 3 and 3 - 2.3. ∀a, b, c ∈ Z [(a | b) ∧ (a | c)] → [(b | c) ∨ (c | b)]Answer: FALSE.Counterexample: Let a = 2, b = 4, and c = 6.Then a | b and a | c since 2 | 4 and 2 | 6. However, 4 - 6 and 6 - 4.4. If a | b and b | c, then a | c, for any integers a, b, and c.Answer: TRUE.Let a, b, and c be arbitrary integers.Assume a | b and b | c.Then ∃m, n ∈ Z am = b ∧ bn = c.Since am = b, then (am)n = c, which means a(mn) = c by substitution and asso ciativity.Since mn ∈ Z by closure of the integers under multiplication,a | c by definition of divides.∀a, b, c ∈ Z (a | b) ∧ (b | c) → (a | c) by closing of conditional world and generalizing fromthe generic particular.5. If x is an odd integer, then x2− 1 is divisible by 4.1Answer: TRUE.Let x be an arbitrary odd integer.Since x is odd, ∃k ∈ Z x = 2k + 1.Then x2− 1 = (2k + 1)2− 1 = 4k2+ 4k + 1 − 1 = 4k2+ 4k by substitution and algebra.Then x2− 1 = 4(k2+ k) by algebra.Since k2+ k ∈ Z by closure of the integers under positive exponentiation and addition,4 | (x2− 1) by definition of divides.∀x ∈ Zodd4 | (x2− 1) by generalizing from the generic particular.6. If a prime greater than 2 can be represented as 3k + 2 for some integer k, then that primecan be represented as 6m + 5 for some integer m.Answer: TRUE.Let p be an arbitrary prime greater than 2.Assume ∃k ∈ Z p = 3k + 2.Since k is an integer, k is either even or odd.Assume k is even.Then ∃g ∈ Z k = 2g.Then p = 3k + 2 = 3(2g) + 2 = 6g + 2 = 2(3g + 1) by substitution and algebra.Since 3g + 1 ∈ Z by closure of the integers under multiplication and addition,2 | p by definition of divides.However, this is a contradiction since p is a prime greater than 2.So we know k is not even, and therefore, k is odd.Then ∃g ∈ Z k = 2g + 1. Then p = 3k + 2 = 3(2g + 1) + 2 = 6g + 3 + 2 = 6g + 5 bysubstitution and algebra.∀p ∈ Zprime>2(∃k ∈ Z p = 3k + 2) → (∃m ∈ Z p = 6m + 5) by closing conditional worldand generalizing from the generic particular.7. For any integer n, n36≡42.Answer: TRUE.Let n be an arbitrary integer.Assume (by the way of contradiction) that n3≡42.Therefore 4 | (n3− 2) by definition of mod, which means∃k ∈ Z n3= 4k + 2.By the quotient-remainder theorem, there exist unique integers q and r such that n = 4q +rand 0 ≤ r < 4.Case 1: assume r = 0.So n = 4q by substitution.Then n3= (4q)3= 64q3by substitution and algebra.Since n3= 4k + 2, then we know 4k + 2 = 64q3by substitution.Then 1/2 = 16q3− k by algebra.We know that 16q3− k ∈ Z by closure of the integers under multiplication, addition, andpositive exponentiation, however, 1/2 6∈ Z. Contradiction.Case 2: assume r = 1.So n = 4q + 1 by substitution.Then n3= (4q + 1)3= 64q3+ 48q2+ 12q + 1 by substitution and algebra.Since n3= 4k + 2, then we know 4k + 2 = 64q3+ 48q2+ 12q + 1 by substitution.2Then 1/4 = 16q3+ 12q2+ 3q − k by algebra.We know that 16q3+ 12q2+ 3q − k ∈ Z by closure of the integers under multiplication,addition, and positive exponentiation, however, 1/4 6∈ Z. Contradiction.Case 3: assume r = 2.So n = 4q + 2 by substitution.Then n3= (4q + 2)3= 64q3+ 96q2+ 48q + 8 by substitution and algebra.Since n3= 4k + 2, then we know 4k + 2 = 64q3+ 96q2+ 48q + 8 by substitution.Then 1/4 = 16q3+ 24q2+ 12q + 2 − k by algebra.We know that 16q3+ 24q2+ 12q + 2 − k ∈ Z by closure of the integers under multiplication,addition, and positive exponentiation, however, 1/2 6∈ Z. Contradiction.Case 3: assume r = 3.So n = 4q + 3 by substitution.Then n3= (4q + 3)3= 64q3+ 144q2+ 108q + 27 by substitution and algebra.Since n3= 4k + 2, then we know 4k + 2 = 64q3+ 144q2+ 108q + 27 by substitution.Then −25/4 = 16q3+ 36q2+ 27q − k by algebra.We know that 16q3+ 36q2+ 27q − k ∈ Z by closure of the integers under multiplication,addition, and positive exponentiation, however, −25/4 6∈ Z. Contradiction.So all four cases lead to contradictions. However, one of the cases must be true by thequotient-remainder theorem, which is in itself another contradiction, which means our orig-inal assumption must be false.So n36≡42.∀n ∈ Z n36≡42 by generalizing from the generic particular.8. ∀x ∈ Zeven(3 - x) → (4 | x2)Answer: Let x be an arbitrary even integer.Assume that 3 - x.By the quotient-remainder theorem, there exist unique integers q and r such that x = 3q +rand 0 ≤ r < 3.So (x = 3q) ∨ (x = 3q + 1) ∨ (x = 3q + 2) by enumerating all the possibilities.Case 1: assume x = 3q.Then 3 | x by definition of divides, which is a contradiction. So case 1 can never occur.Case 2: assume x = 3q + 1.Since q is an integer, q is either odd or even.Assume that q is even.Then ∃k ∈ Z q = 2k by definition of even.Then x = 3(2k) + 1 = 6k + 1 …


View Full Document

UMD CMSC 250 - Homework 5 Answers

Download Homework 5 Answers
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework 5 Answers and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 5 Answers 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?