Report

Chapter 5 Properties of Whole Numbers Some preliminary definitions If we have whole numbers a, b, and c such that a×b=c then we say that 1. a divides c or 2. a is a factor of c or 3. a is a divisor of c and 4. c is a multiple of a or 5. c is divisible by a (We can always interchange a with b.) Properties of Divisibility Suppose that a, m, n, k are whole numbers where a ≠ 0. 1. If a divides m and a divides n, then a divides (m + n). 2. If a divides m but a does not divide n, then a does not divide (m + n). 3. If a divides both m and n, and m ≥ n, then a divides (m – n). 4. If a divides m but a does not divide n, and m ≥ n, then a does not divide (m – n). 5. If a divides m, then a divides km. Transitive Property of Divisibility If a, b, c are non zero whole numbers such that a divides b and b divides c, then a divides c. Important remarks: 1. 0 is divisible by any non-zero number, 2. No number is divisible by 0. Different types of whole numbers a. Prime numbers A number is prime if it is > 1 and it is only divisible by 1 and itself. e.g. 2, 3, 5, 7, 11, … b. Composite numbers A number is composite if it can be written as the product of two smaller whole numbers. e.g. 4 (=2×2), 6 (=2×3), 10 (=2×5), … c. Identities The numbers 0 and 1 are not prime nor composite, they are just identities for respective operations. Prime numbers play an important role within the whole numbers because they are the primary components. More precisely, we have the following Theorem Every whole number bigger than 1 is either a prime number or a product of prime numbers. (in other words, the prime numbers can generate all whole numbers bigger than 1 by multiplication.) Factorization Trees According to the previous theorem, if a number n is not prime, we must be able to break it down to a product of prime numbers. Here is how, 60 6 2 3 This tree is by no means unique, we can easily make another one, such as 10 2 5 However, the collection of prime numbers we get from the “leaves” of the tree is always the same. In other words, 60 = 2×2×3×5 no matter how we factorize it. 60 2 30 5 6 2 3 Unique Factorization Theorem Any whole number bigger than 1 can be factorized into a product of prime numbers in exactly one way if we list its prime factors from small to large. Example: 3780 = 2×2×3×3×3×5×7 Test for Primeness (i.e. a faster way to determine whether a whole number is prime or not) Theorem A whole number n ( >1) is prime if it is not divisible by any prime number n Example: Is 179 a prime number? a. compute 179 which is approx. 13.379 b. all prime numbers 13.3 are 2, 3, 5, 7, 11, 13 c. Is 179 divisible by 2? No Is 179 divisible by 3? No Is 179 divisible by 5? No Is 179 divisible by 7? No Is 179 divisible by 11? No Is 179 divisible by 13? No Therefore 179 is prime. (Note: this reduce the work from checking 177 numbers to just 6 numbers!) Divisibility Tests Test of divisibility for 2: A whole number n is divisible by 2 if and only if its last digit is divisible by 2 (i.e. even) Test of divisibility for 5: A whole number n is divisible by 5 if and only if its last digit is divisible by 5 (i.e. 0 or 5) Divisibility Tests Test of divisibility for 4: A whole number n is divisible by 4 if and only if the number represented by its last two digits is divisible by 4. Examples: 21732 is divisible by 4 because 32 is divisible by 4. Note that neither the digit 3 nor 2 is divisible by 4. It is the number 3×10+2 that is divisible by 4. Hence it is wrong to say that the last two digits are divisible by 4. 44442 is not divisible by 4 because 42 is not. Divisibility Tests Test of divisibility for 8: A whole number n is divisible by 8 if and only if The number represented by its last three digits is divisible by 8. Examples: 201432 is divisible by 8 because 432 is divisible by 8, 716510 is not divisible by 8 because 510 is not divisible by 8 Divisibility Tests Test of divisibility for 3: A whole number n is divisible by 3 if and only if the sum of its digits is divisible by 3. Example: 71653092 is divisible by 3 because 7 +1 + 6 + 5 + 3 + 0 + 9 + 2 = 33 Test of divisibility for 9: A whole number n is divisible by 9 if and only if the sum of its digits is divisible by 9. Divisibility Tests Test of divisibility for 11: A whole number n is divisible by 11 if and only if the alternate sum of its digits is divisible by 11. Examples: Let’s first look at all 2-digit multiples of 11, 11, 22, 33, 44, 55, 66, 77, 88, 99 The difference of the two digits is 0, hence divisible by 11. Divisibility Tests Test of divisibility for 11: A whole number n is divisible by 11 if and only if the alternate sum of its digits is divisible by 11. Examples: 3-digit multiples of 11 121, 132, 154, 165, …, 957, 968, 979, 990. You should see that 1st digit – 2nd digit + 3rd digit is divisible by 11. Divisibility Tests Test of divisibility for 11: A whole number n is divisible by 11 if and only if the alternate sum of its digits is divisible by 11. More examples: 72952 is divisible by 11 because 7 – 2 + 9 – 5 + 2 = 11, which is divisible by 11. 56823 is not divisible by 11 because 5 – 6 + 8 – 2 + 3 = 8, which is not divisible by 11. Greatest Common Factor (GCF) Definition: The GCF of two whole numbers a and b is the largest whole number c that can divide into both a and b. Methods for finding GCF(a, b) (I) Set intersection method – depends on listing all factors of a and b. Greatest Common Factor (GCF) Definition: The GCF of two whole numbers a and b is the largest whole number c that can divide into both a and b. Methods for finding GCF(a, b) (I) Set intersection method – depends on listing all factors of a and b. example: to find the GCF(12, 18) Greatest Common Factor (GCF) Definition: The GCF of two whole numbers a and b is the largest whole number c that can divide into both a and b. Methods for finding GCF(a, b) (I) Set intersection method – depends on listing all factors of a and b. example: to find the GCF(12, 18) factors of 12: 1, 2, 3, 4, 6, 12. Greatest Common Factor (GCF) Definition: The GCF of two whole numbers a and b is the largest whole number c that can divide into both a and b. Methods for finding GCF(a, b) (I) Set intersection method – depends on listing all factors of a and b. example: to find the GCF(12, 18) factors of 12: 1, 2, 3, 4, 6, 12. factors of 18: 1, 2, 3, 6, 9, 18. Greatest Common Factor (GCF) Definition: The GCF of two whole numbers a and b is the largest whole number c that can divide into both a and b. Methods for finding GCF(a, b) (I) Set intersection method – depends on listing all factors of a and b. example: to find the GCF(12, 18) factors of 12: 1, 2, 3, 4, 6, 12. factors of 18: 1, 2, 3, 6, 9, 18. Clearly the red numbers are the common factors and 6 is the largest, GCF(12, 18) = 6 Greatest Common Factor (GCF) Methods for finding GCF(a, b) (method I is straight forward and easy to learn but slow for larger numbers) (II) Factorization method – depends on the complete factorization of a and b. example: to find the GCF(24, 180) 24 = 2×2×2×3, 180 = 2×2×3×3×5 and by the “Greedy algorithm”, we pick all the prime factors common to both numbers (including multiplicities) GCF(24, 180) = 2×2×3 (method II is still difficult to use if the numbers are too large and difficult to factorize.) (III) Euclidean Algorithm – depends on reducing large numbers to smaller ones. Theory: if a > b, then GCF(a, b) = GCF(a - b, b) in other words, we can reduce the larger number by subtracting it with the smaller one, without changing the GCF. (click to scroll up) (method II is still difficult to use if the numbers are too large and difficult to factorize.) (III) Euclidean Algorithm – depends on reducing large numbers to smaller ones. Theory: if a > b, then GCF(a, b) = GCF(a - b, b) in other words, we can reduce the larger number by subtracting it with the smaller one, without changing the GCF. (III) Euclidean Algorithm – depends on reducing large numbers to smaller ones. Theory: if a > b, then GCF(a, b) = GCF(a - b, b) in other words, we can reduce the larger number by subtracting it with the smaller one, without changing the GCF. Example: GCF(481, 296) = GCF(481 – 296, 296) = GCF(185, 296) = GCF(185, 296 – 185) = GCF(185, 111) = GCF(74, 111) = GCF(74, 37) = GCF(37, 37) = 37 Lowest Common Multiple (LCM) Definition: The LCM of two whole numbers a and b is the smallest whole number c that is divisible by both a and b. Methods for finding LCM(a, b) (I) Set intersection method – depends on listing small multiples of a and b. example: to find the LCM(15, 24) multiples of 15: multiples of 24: Lowest Common Multiple (LCM) Definition: The LCM of two whole numbers a and b is the smallest whole number c that is divisible by both a and b. Methods for finding LCM(a, b) (I) Set intersection method – depends on listing small multiples of a and b. example: to find the LCM(15, 24) multiples of 15: 15, 30, 45, 60, 75, 90, 105, multiples of 24: 24, 48, 72, 96, 120, Lowest Common Multiple (LCM) Definition: The LCM of two whole numbers a and b is the smallest whole number c that is divisible by both a and b. Methods for finding LCM(a, b) (I) Set intersection method – depends on listing small multiples of a and b. example: to find the LCM(15, 24) multiples of 15: 15, 30, 45, 60, 75, 90, 105, 120. multiples of 24: 24, 48, 72, 96, 120, Lowest Common Multiple (LCM) Definition: The LCM of two whole numbers a and b is the smallest whole number c that is divisible by both a and b. Methods for finding LCM(a, b) (I) Set intersection method – depends on listing small multiples of a and b. example: to find the LCM(15, 24) multiples of 15: 15, 30, 45, 60, 75, 90, 105, 120. multiples of 24: 24, 48, 72, 96, 120, Therefore LCM(15, 24) = 120. Lowest Common Multiple (LCM) Methods for finding LCM(a, b) (II) Factorization method – a “thrifty” algorithm example: to find the LCM(875, 1225) 875 = 5×5×5×7 1225 = 5×5×7×7 Analogy: Your math teacher requires you to bring 3 pencils and 1 highlighter to class, your History teacher requires you to bring 2 pencils and 2 highlighters. What is the minimum set of pens you need to bring if you have both classes in one day? Ans: 3 pencils and 2 highlighters. Lowest Common Multiple (LCM) Methods for finding LCM(a, b) (II) Factorization method – a “thrifty” algorithm example: to find the LCM(875, 1225) 875 = 5×5×5×7 1225 = 5×5×7×7 Analogy: Your math teacher requires you to bring 3 pencils and 1 highlighter to class, your History teacher requires you to bring 2 pencils and 2 highlighters. What is the minimum set of pens you need to bring if you have both classes in one day? Ans: 3 pencils and 2 highlighters. LCM(875, 1225) = 5×5×5×7×7 Lowest Common Multiple (LCM) Methods for finding LCM(a, b) (II) Factorization method – Another example: to find the LCM(60, 126) 60 = 2×2×3×5 126 = 2×3×3×7 Answer: 2×2×3×3×5×7 Lowest Common Multiple (LCM) Methods for finding LCM(a, b) (III) “Mechanical method” – using a formula ab LCM (a, b) = GCF (a, b) Example: Find the LCM of 481 and 296. Answer: we have calculated before that GCF(481, 296) = 37, therefore LCM(481, 296) = (481×296) ÷ 37 = 3848 Lowest Common Multiple (LCM) Example: Your neighbor has two dogs - one named Sparky and one named Skippy. They both like to bark and both have a pattern. Sparky will bark for a while every 15 minutes once started, and Skippy does the same every 18 minutes. One night they both started barking at 9pm because a cat passed by. When did they bark together again that night?