CMSC250, Spring 2004 Homework 6 AnswersDue 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 oryou will lose points.1. Let p1, p2, . . . , pnbe distinct prime numbers such that p1= 2 and n > 1, and let a =p1p2···pn. Prove that a ≡42.Hint: Use the quotient-remainder theorem, and eliminate the other possibilities.Answer: Proof:Let p1, p2, . . . , pnbe distinct prime numbers such that p1= 2 and n > 1, and let a =p1p2···pn. By the quotient-remainder theorem, we know there exist unique integers q andk 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···pnby substitution.We also know that a = 4q = 22q by algebra.Let’s set these two representations of a equal to each other: 2p2···pn= 22q.Let x be the number of factors of 2 in the s tandard factored form of q.So q = 2xq0for some nonnegative integer x and some integer q0, and 2 - q0.So now we have this equality: 2p2···pn= 22+xq0.Since none of the p2, . . . , pnare two (because p1= 2 and all of them are distinct), there isonly one factor of two on the left side. The right s ide has at least two factors of 2, possiblymore. 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 sosimilar.)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 bythe definition of odd.However, since a = 2p2···pnand p2···pn∈ Z by closure of the integers under multiplica-tion, 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 anddisjunctive syllogism three times, we learn that a = 4q + 2.Therefore, a − 2 = 4q by algebra, which means a ≡42 by the definition of mod.2. An integer is called squarefree if it is not divisible by the square of any prime number. Whatcan 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.13. 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 intothose with even exponents and those with odd exponents.a = (pe11pe22···penn) (qd11qd22···qdmm) where pi, qi∈ Zprime, ei, di∈ Znonneg, m ∈ Z+, n ∈Znonneg, 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 standardfactored 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 2xifor some integer xi.Since all of the dj’s are odd, each one can be written as 2yj+ 1 for some integer yj.So a = (p2x11p2x22···p2xnn)(q2y1+11q2y2+12···q2ym+1m) by substitution, and this equalsh(p2x11p2x22···p2xnn)(q2y11q2y22···q2ymm)iq11q12···q1m by algebra, and this equals[(px11px22···pxnn)(qy11qy22···qymm)]2q11q12···q1m by algebra.The first factor is clearly a pe rfect square, and the second term is a squarefree integerbecause 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 isthe 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 greate r than 1 can be written as asthe 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 getbxc ≤ x.If we subtract one from both sides of bxc ≤ x < bxc + 1, we getbxc − 1 ≤ x − 1 < bxc.Since this is an “and” statement, we can use conjunctive simplification and getx − 1 < bxc.Since x − 1 < bxc and bxc ≤ x, by the transitivity of “<”, we can combine these twoinequalities to getx − 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(b) ∀n ≥ 0, rn=nn!Answer: 0, 1, 1, 1/2.6. Reduce each of the following expressions to a single numeric value:(a)4Xi=1−1i2+ i= −4/5.(b)10Yh=0hh! + h + 1= 0.(c)3Xm=1 mYn=1mn!= 15/2.7. Write each of the following using sum and/or product notation:(a) n + 0 − n − 1 + n + 2 − n − 3 + n + 4Answer:4Xi=0(−1)i· (n + i)(b)√5(1) + 2(1 + 2) +√3(1 + 2 + 3) +√2(1 + 2 + 3 + 4) + 1(1 + 2 + 3 + 4 + 5)Answer:5Xi=1√6 − i
View Full Document
Unlocking...