CMSC250 Spring 2004 Homework 5 Answers Due 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 or you will lose points Prove each of the following statements true or false Remember a counterexample may only be used to prove that a for all statement is false and all counterexamples must include specific values 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 generalizing from 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 associativity 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 from the generic particular 5 If x is an odd integer then x2 1 is divisible by 4 1 Answer TRUE Let x be an arbitrary odd integer Since x is odd k Z x 2k 1 Then x2 1 2k 1 2 1 4k 2 4k 1 1 4k 2 4k by substitution and algebra Then x2 1 4 k 2 k by algebra Since k 2 k Z by closure of the integers under positive exponentiation and addition 4 x2 1 by definition of divides x Zodd 4 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 prime can 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 by substitution and algebra p Zprime 2 k Z p 3k 2 m Z p 6m 5 by closing conditional world and generalizing from the generic particular 7 For any integer n n3 6 4 2 Answer TRUE Let n be an arbitrary integer Assume by the way of contradiction that n3 4 2 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 r and 0 r 4 Case 1 assume r 0 So n 4q by substitution Then n3 4q 3 64q 3 by substitution and algebra Since n3 4k 2 then we know 4k 2 64q 3 by substitution Then 1 2 16q 3 k by algebra We know that 16q 3 k Z by closure of the integers under multiplication addition and positive exponentiation however 1 2 6 Z Contradiction Case 2 assume r 1 So n 4q 1 by substitution Then n3 4q 1 3 64q 3 48q 2 12q 1 by substitution and algebra Since n3 4k 2 then we know 4k 2 64q 3 48q 2 12q 1 by substitution 2 Then 1 4 16q 3 12q 2 3q k by algebra We know that 16q 3 12q 2 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 64q 3 96q 2 48q 8 by substitution and algebra Since n3 4k 2 then we know 4k 2 64q 3 96q 2 48q 8 by substitution Then 1 4 16q 3 24q 2 12q 2 k by algebra We know that 16q 3 24q 2 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 64q 3 144q 2 108q 27 by substitution and algebra Since n3 4k 2 then we know 4k 2 64q 3 144q 2 108q 27 by substitution Then 25 4 16q 3 36q 2 27q k by algebra We know that 16q 3 36q 2 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 the quotient remainder theorem which is in itself another contradiction which means our original assumption must be false So n3 6 4 2 n Z n3 6 4 2 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 r and 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 by algebra and substitution However we claimed that x was even which means m Z x 2m Then 6k 1 2m …
View Full Document
Unlocking...