CMSC 250 Quiz #7 KEY Wednesday, Mar. 10, 2004Write all answers legibly in the space provided. The number of points possible for each question is indicatedin square brackets – the total number of p oints on the quiz is 30, and you will have exactly 20 minutes tocomplete this quiz. You may not use calculators, textbooks or any other aids during this quiz.1. [20 pnts.] Disprove by counter example or Prove each of the following:a. The sum of any rational number and any integer is rational.show: ∀r ∈ Q, ∀m ∈ Z, r + m ∈ QPROOF:Let r ∈ Q and m ∈ Z be arbitrary.Since r ∈ Q, ∃a, b ∈ Z where b 6= 0, r =abby definition of rationalr + m =ab+ m by substitution=ab+mbbby multiplying second term bybb=a+mbbby moving them over the common denominatora + mb ∈ Z because of closure of Z during the operations of + and *b ∈ Z where b 6= 0 as defined abovetherefore r + m ∈ Q because it is a quotient of integers as required by the definition of ra-tional.∀r ∈ Q, ∀m ∈ Z, r + m ∈ Q by generalizing from the Generic Particular.b. For every integer n, n2− n + 3 ≡21∀n ∈ Z, n2− n + 3 ≡21PROOF:Let n be arbitrary in Z.By the Quotient Remainder Threorem, we know that ∃q ∈ Z , n = 2q + 0 ∨ n = 2q + 1Case 1 (n = 2q + 0):n2− n + 3 = (2q)2− (2q) + 3 by substitutionn2− n + 3 = 4q2− 2q + 2 + 1 by multiplication and additionn2− n + 3 = 2(2q2− q + 1) + 1 by factorringSince 2q2− q + 1 ∈ Z by closure of integers in multiplication and addition,∃j ∈ Z, n2− n + 3 = 2j + 1 by substitution.(n2− n + 3) − 1 = 2j by subtracting 1 from both sides.2|[(n2− n + 3) − 1] by definition of divides.n2− n + 3 ≡21 by definition of equivalence in a modCase 2 (n = 2q + 1):n2− n + 3 = (2q + 1)2− (2q + 1) + 3 by substitutionn2− n + 3 = 4q2+ 4q + 1 − 2q − 1 + 3 by multiplicationn2− n + 3 = 4q2+ 2q + 2 + 1 by algebran2− n + 3 = 2(2q2+ q + 1) + 1 by factorringSince 2q2+ q + 1 ∈ Z by closure of integers in multiplication and addition∃k ∈ Z, n2− n + 3 = 2k + 1 by substitution(n2− n + 3) − 1 = 2k by subtracting 1 from both sides.2|[(n2− n + 3) − 1] by definition of divides.n2− n + 3 ≡21 by definition of equivalence in a modSince the quotient remainder theorem tells us that these are the only two possibilities andboth of these lead to the fact that n2− n + 3 ≡21, by dilemma we know that n2− n + 3 ≡21∀n ∈ Z, n2− n + 3 ≡21 by generalizing from the Generic Particular.2. [4 pnts.] Write the standard factored form of 1050:1050 = 21∗ 31∗ 52∗ 713. [6 pnts.] Use the unique factorization theorem and suppose that m is an integer such that5 ∗ 4 ∗ 3 ∗ 2 ∗ m = 10 ∗ 11 ∗ 12 ∗ 13Circle Yes or No for each of the following: Yes means that this is something that must be true, Nomeans it doesn’t necessarily need to be true:a) 10|m YES (NO)b) 11|m (YES) NOc) 12|m YES (NO)d) 13|m (YES) NOe) 24|m YES (NO)f) 143|m (YES)
View Full Document
Unlocking...