CMSC250 Spring 2004 Homework 6 Answers Due Wednesday March 10 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 1 Let p1 p2 pn be distinct prime numbers such that p1 2 and n 1 and let a p1 p2 pn Prove that a 4 2 Hint Use the quotient remainder theorem and eliminate the other possibilities Answer Proof Let p1 p2 pn be distinct prime numbers such that p1 2 and n 1 and let a p1 p2 pn By the quotient remainder theorem we know there exist unique integers q and k such that a 4q k 0 k 4 Then a 4q a 4q 1 a 4q 2 a 4q 3 by enumerating the possibilities Case 1 a 4q We know that a 2p2 pn by substitution We also know that a 4q 22 q by algebra Let s set these two representations of a equal to each other 2p2 pn 22 q Let x be the number of factors of 2 in the standard factored form of q So q 2x q 0 for some nonnegative integer x and some integer q 0 and 2 q 0 So now we have this equality 2p2 pn 22 x q 0 Since none of the p2 pn are two because p1 2 and all of them are distinct there is only one factor of two on the left side The right side has at least two factors of 2 possibly more Therefore by the unique factorization theorem 1 2 x By algebra x 1 which is a contradiction since we stated x is a nonnegative integer Case 2 a 4q 1 or q 4q 3 We re combining these two cases because they are so similar Since 1 and 3 are both odd we can write a as 4q 2k 1 for some integer k a 2 2q k 1 by algebra Since 2q k Z by closure of the integers under multiplication and addition a is odd by the definition of odd However since a 2p2 pn and p2 pn Z by closure of the integers under multiplication a is even by the definition of even This is a contradiction since no integer can be both even and odd So a 6 4q and a 6 4q 1 and a 6 4q 3 By applying conjunctive simplification and disjunctive syllogism three times we learn that a 4q 2 Therefore a 2 4q by algebra which means a 4 2 by the definition of mod 2 An integer is called squarefree if it is not divisible by the square of any prime number What can you deduce about the standard factored form of a squarefree number Hint Examine the exponents Answer All the exponents in the standard factored form must be either zero or one 1 3 Prove that any integer a 1 can be written as a either perfect square a squarefree integer or the product of a squarefree integer and a perfect square Answer Proof Let a be an integer greater than 1 Assume that a cannot be written as either a perfect square nor a squarefree integer Since a is an integer it can be factored over the primes We will split the prime factors into those with even exponents and those with odd exponents dm where p q Zprime e d Znonneg m Z n a pe11 pe22 penn q1d1 q2d2 qm i i i i nonneg Z and all the ei s are even and the dj s are odd We can do this for the following reasons Since a is not a perfect square there must be at least one odd exponent in the standard factored form Since a is not squarefree there must be some exponent that is greater than one Since all of the ei s are even each one can be written as 2xi for some integer xi Since all of the dj s are odd each one can be written as 2yj 1 for some integer yj 2y1 1 2y2 1 2ym 1 2x1 2x2 2xn So q2 i qm by substitution and this equals h a p1 p2 pn q1 2y 2y 2y 2x1 2x2 1 by algebra and this equals p1 p2 pn2xn q1 1 q2 2 qm m q11 q21 qm ym 2 1 1 1 by algebra px1 1 px2 2 pxnn q1y1 q2y2 qm q1 q2 qm The first factor is clearly a perfect square and the second term is a squarefree integer because all of the exponents in the standard factored form are 1 So a can be written as as the product of a squarefree integer and a perfect square By closing the conditional world if a is neither a perfect square nor squarefree then it is the product of a squarefree integer and a perfect square By applying the definition of implication a is either a perfect square a squarefree integer or the product of a squarefree integer and a perfect square By generalizing from the generic particular any integer greater than 1 can be written as as the product of a squarefree integer and a perfect square 4 Prove that for all real numbers x x 1 bxc x Answer Proof Let x be a real number By the definition of floor bxc x bxc 1 Since this is an and statement we can use conjunctive simplification and get bxc x If we subtract one from both sides of bxc x bxc 1 we get bxc 1 x 1 bxc Since this is an and statement we can use conjunctive simplification and get x 1 bxc Since x 1 bxc and bxc x by the transitivity of we can combine these two inequalities to get x 1 bxc x 5 Write the first four terms of each of the following sequences a j 1 sj j j 1 Answer 2 6 12 20 2 n n Answer 0 1 1 1 2 b n 0 rn 6 Reduce each of the following expressions to a single numeric value 4 X 1 4 5 a 2 i i i 1 10 Y h 0 h h 1 h 0 3 m X Y m 15 2 c n b m 1 n 1 7 Write each of the following using sum and or product notation a n 0 n 1 n 2 n 3 n 4 4 X Answer 1 i n i b i 0 5 1 2 1 2 3 1 2 3 2 1 2 3 4 1 1 2 3 4 5 5 i X X 6 i Answer j i 1 j 1 3
View Full Document
Unlocking...