Report

Quotient-Remainder Theory, Div and Mod If and are integers and > 0, then = and = ⟺ = + where and are integers and 0 ≤ < . Quotient: q = = Reminder: r = = − 1 Exercise Prove that for all integers a and b, if a mod 7 = 5 and b mod 7 = 6 then ab mod 7 = 2. What values are , , and ? 2 Exercise Prove that for all integers a and b, if a mod 7 = 5 and b mod 7 = 6 then ab mod 7 = 2. Hint: = 7 = 7 + 5, b = 7 +6 = 7 + 5 7 + 6 = 49 + 42 + 35 + 30 = 7 7 + 6 + 3 + 4 + 2 3 Floor & Ceiling Definition: • Floor: If is a real number and is an integer, then = ⟺ ≤ <+1 • Ceiling: if is a real number and is an integer, then = ⟺ −1< ≤ +1 floor of = −1 ceiling of = 4 Relations between Proof by Contradiction and Proof by Contraposition • To prove a statement ∀ in , if then () • Proof by contraposition proves the statement by giving a direct proof of the equivalent statement ∀ in , if is false then is false Suppose is an arbitrary element of such that ~() Sequence of steps ~() • Proof by contradiction proves the statement by showing that the negation of the statement leads logically to a contradiction. Suppose ∃ in such that () and ~() Same sequence of steps Contradiction: () and ~() 5 Summary of Chapter 4 • Number theories: – Even, odd, prime, and composite – Rational, divisibility, and quotient-remainder theorem – Floor and ceiling – The irrationality of 2 and gcd • Proofs: – Direct proof and counterexample – Indirect proof by contradiction and contraposition 6 The Irrationality of 2 How to proof: • Direct proof? • Proof by contradiction? • Proof by contraposition? If is a real number, then is rational ⇔ ∃ integers and such that = and ≠ 0. A real number that is not rational is irrational. 7 The Irrationality of 2 Proof by contradiction: Starting point: Negation: 2 is rational. To show: A contradiction. 2 = , where and are integers with no common factors and ≠ 0, by definition of rational. 2 = 22 , by squaring and multiplying both sides with 2 2 is even, then is even. Let = 2 for some integer . (2)2 = 4 2 = 22 , by substituting = 2 into 2 = 22 . 2 is even, and so is even. Hence both and have a common factor of 2. 8 Irrationality of 1 + 3 2 Proof by contradiction: Starting point: Negation: 1 + 3 2 is rational. To show: A contradiction. 9 Irrationality of 1 + 3 2 Proof by contradiction: By definition of rational, 1 + 3 2 = for some integers and with ≠ 0. It follows that =− − = 3 2= −1 by subtracting 1 from both sides by substitution by the rule for subtracting fractions with a common denominator Hence, 2= − 3 by dividing both sides by 3. − and 3 are integers and 3 ≠ 0 by the zero product property. Hence 2 is quotient of the two integers − and 3 with 3 ≠ 0, so 2 is rational by the definition of rational. This contradicts the fact that 2 is irrational. 10 Property of a Prime Divisor Proposition 4.7.3 For any integer and any prime number , if | then | ( + 1) If a prime number divides an integer, then it does not divide the next successive integer. Starting point: there exists an integer and a prime number such that | and | ( + 1). To show: a contradiction. = and + 1 = for some integers and by definition of divisibility. It follows that 1 = ( + 1) − = − = ( − ), − = 1/, by dividing both sides with . > 1 because is prime, hence, 1/ is not an integer, thus − is not an integer, which is a contradict − is an integer since and are integers. if and are integers and ≠ 0: | ⟺ ∃ an integer such that = ∙ Infinitude of the Primes Theorem 4.7.4 Infinitude of the Primes The set of prime numbers is infinite. Proof by contradiction: Starting point: the set of prime number is finite. To show: a contradiction. Assume a prime number is the largest of all the prime numbers 2, 3, 5, 7, 11, . . . , . Let be the product of all the prime numbers plus 1: = (2 · 3 · 5 · 7 · 11 · · · ) + 1 Then > 1, and so, by Theorem 4.3.4 (any integer larger than 1 is divisible by a prime number) , is divisible by some prime number q. Because q is prime, q must equal one of the prime numbers 2, 3, 5, 7, 11, . . . , . Thus, by definition of divisibility, divides 2 · 3 · 5 · 7 · 11 · · · , and so, by Proposition 4.7.3, does not divide (2 · 3 · 5 · 7 · 11 · · · ) + 1, which equals . Hence N is divisible by q and N is not divisible by q, and we have reached a contradiction. [Therefore, the supposition is false and the theorem is true.] 12 Greatest Common Divisor (GCD) • The greatest common divisor of two integers a and b is the largest integer that divides both and . Definition Let and be integers that are not both zero. The greatest common divisor of and , denoted gcd(a, b), is that integer with the following properties: 1. is common divisor of both a and b, in other words, | , and | . 2. For all integers , if is a common divisor of both and , then is less than or equal to . In other words, for all integers , if | , and |, then c ≤ . Exercise: • gcd 72,63 = 9, since 72 = 9 ∙ 8 and 63 = 9 ∙ 7 • gcd 1020 , 630 = 220 , since 1020 = 220 ∙ 520 and 630 = 230 ∙ 330 13 Greatest Common Divisor (GCD) Lemma 4.8.1 If is a positive integer, then gcd(, 0) = . Proof: Suppose is a positive integer. [We must show that the greatest common divisor of both and 0 is .] 1. is a common divisor of both and 0 because r divides itself and also divides 0 (since every positive integer divides 0). 2. No integer larger than can be a common divisor of and 0 (since no integer larger than can divide ). Hence is the greatest common divisor of and 0. 14 Greatest Common Divisor (GCD) Lemma 4.8.2 If and are any integers not both zero, and if and are any integers such that = + , then gcd(, ) = gcd(, ) Proof: [The proof is divided into two sections: (1) proof that gcd(, ) ≤ gcd(, ), and (2) proof that gcd(, ) ≤ gcd(, ). Since each gcd is less than or equal to the other, the two must be equal.] 1. gcd(, ) ≤ gcd(, ): a. [We will first show that any common divisor of and is also a common divisor of and .] Let and be integers, not both zero, and let be a common divisor of and . Then | and | , and so, by definition of divisibility, = and = , for some integers and . Now substitute into the equation = + to obtain = () + . 15 Greatest Common Divisor (GCD) Lemma 4.8.2 If and are any integers not both zero, and if and are any integers such that = + , then gcd(, ) = gcd(, ) Proof (cont’): 1. gcd(, ) ≤ gcd(, ): a. [We will first show that any common divisor of and is also a common divisor of and .] = () + . Then solve for : = − () = ( − ). But − is an integer, and so, by definition of divisibility, | . Because we already know that | , we can conclude that is a common divisor of and [as was to be shown]. 16 Greatest Common Divisor (GCD) Lemma 4.8.2 If and are any integers not both zero, and if and are any integers such that = + , then gcd(, ) = gcd(, ) Proof (cont’): 1. gcd(, ) ≤ gcd(, ): b. [Next we show that gcd(, ) ≤ gcd(, ).] By part (a), every common divisor of and is a common divisor of and . It follows that the greatest common divisor of and is defined because and are not both zero, and it is a common divisor of and . But then gcd(, ) (being one of the common divisors of and ) is less than or equal to the greatest common divisor of and : gcd(, ) ≤ gcd(, ). 2. gcd(, ) ≤ gcd(, ): The second part of the proof is very similar to the first part. It is left as an exercise. 17 The Euclidean Algorithm • Problem: – Given two integer A and B with > ≥ 0, find gcd(, ) • Idea: – The Euclidean Algorithm uses the division algorithm repeatedly. – If B=0, by Lemma 4.8.1 we know gcd(, ) = . – If B>0, division algorithm can be used to calculate a quotient and a remainder : = + where 0 ≤ < – By Lemma 4.8.2, we have gcd(, ) = gcd(, ), where and are smaller numbers than and . • gcd(, ) = gcd(, ) = ⋯ = gcd(, 0) = = 18 The Euclidean Algorithm - Exercise Use the Euclidean algorithm to find gcd(330, 156). 19 The Euclidean Algorithm - Exercise Use the Euclidean algorithm to find gcd(330, 156). Solution: gcd(330,156) = gcd(156, 18) 330 mod 156 = 18 = gcd(18, 12) 156 mod 18 = 12 = gcd(12, 6) 18 mod 12 = 6 = gcd(6, 0) 12 mod 6 = 0 =6 20 An alternative to Euclidean Algorithm If ≥ > 0, then gcd(, ) = gcd(, − ) 21 An alternative to Euclidean Algorithm If ≥ > 0, then gcd(, ) = gcd(, − ) Hint: Part 1: proof gcd(, ) ≤ gcd(, − ) every common divisor of a and b is a common divisor of b and a-b Part 2: proof gcd(, ) ≥ gcd(, − ) every common divisor of b and a-b is a common divisor of a and b. 22 Homework #5 Problems Converting decimal to rational numbers. 4.2.2: 4.6037 4.2.7: 52.4672167216721… 23 Homework #5 Problems 1. Converting decimal to rational numbers. 4.2.2: 4.6037 Solution: 4.6037 = 4.6037 10000 ∗ 10000 = 46037 10000 4.2.7: 52.4672167216721… Solution: let X = 52.4672167216721 . . . 100000x = 5246721.67216721…. 10x = 524.67216721… 100000x – 10x = 5246197 X = 5246197 / 99990 24 Exercise Prove that for any nonnegative integer , if the sum of the digits of is divisible by 9, then is divisible by 9. Hint: by the definition of decimal representation = 10 + −1 10−1 + ⋯ + 1 101 + 0 where is nonnegative integer and all the are integers from 0 to 9 inclusive. = 10 + −1 10−1 + ⋯ + 1 101 + 0 = (9999 ⋯ 999 + 1) + −1 (9999 ⋯ 999 + 1) + ⋯ + 1 (9 + 1) + 0 9′ −1 9′ = 9 11 ⋯ 11 + −1 11 ⋯ 11 + ⋯ + 1 + + −1 + ⋯ + 1 + 0 1′ −1 1′ = an integer divisible by 9 + the sum of the digits of 25 Homework #5 Problems Theorem: The sum of any two even integers equals 4k for some integer k. “Proof: Suppose m and n are any two even integers. By definition of even, m = 2k for some integer k and n = 2k for some integer k. By substitution, m + n = 2k + 2k = 4k. This is what was to be shown.” What’s the mistakes in this proof? 26