5.1 Number Theory 215 Rules of Divisibility Did You Know? The Long-Lost Factoring Machine m Factoring Machine In 1989, Jeffrey Shallit of the University of Waterloo came across an article in a 1920 French journal regarding a machine that was built in 1914 for factoring numbers. Eugene Oliver Carissan, an amateur mathematician who had invented the machine, wrote the article. After reading the article, Shallit wondered whatever became of the factoring machine. After considerable searching, Shallit found the machine in a drawer of an astronomical observatory in Floirac, France. The machine was in good condition, and it still worked. By rotating the machine by a hand crank at two revolutions per minute, an operator could process 35 to 40 numbers per second. Carissan needed just 10 minutes to prove that 708,158,977 is a prime number, an amazing feat in precomputer times. The machine is now housed at the Conservatoire National des Arts et Métiers in Paris. Divisible by Test Example 2 The number is even. 924 is divisible by 2, since 924 is even. 3 The sum of the digits of the number is divisible by 3. 924 is divisible by 3, since the sum of the digits is 9 2 4 15, + + = and 15 is divisible by 3. 4 The number formed by the last two digits of the number is divisible by 4. 924 is divisible by 4, since the number formed by the last two digits, 24, is divisible by 4. 5 The number ends in 0 or 5. 265 is divisible by 5, since the number ends in 5. 6 The number is divisible by both 2 and 3. 924 is divisible by 6, since it is divisible by both 2 and 3. 8 The number formed by the last three digits of the number is divisible by 8. 5824 is divisible by 8, since the number formed by the last three digits, 824, is divisible by 8. 9 The sum of the digits of the number is divisible by 9. 837 is divisible by 9, since the sum of the digits, 18, is divisible by 9. 10 The number ends in 0. 290 is divisible by 10, since the number ends in 0. Note that the chart does not list rules for the divisibility for the number 7. The rule for 7 is given in Exercise 92 on page 223. You may find after using the rule that the easiest way to check divisibility by 7 is simply to perform the division. The test for divisibility by 6 is a particular case of the general statement that the product of two prime divisors of a number is a divisor of the number. Thus, for example, if both 3 and 5 divide a number, then 15 will also divide the number. Example 1 Using the Divisibility Rules Determine whether 724,344 is divisible by a) 2 b) 3 c) 4 d) 5 e) 6 f) 8 g) 9 h) 10 Solution a) 2: Since 724,344 is even, it is divisible by 2. b) 3: The sum of the digits of 724,344 is 7 2 4 3 4 4 24. + + + + + = Since 24 is divisible by 3, the number 724,344 is divisible by 3. c) 4: The number formed by the last two digits is 44. Since 44 is divisible by 4, the number 724,344 is divisible by 4. d) 5: Since 724,344 does not end in either a 0 or 5, the number 724,344 is not divisible by 5. e) 6: Since 724,344 is divisible by both 2 and 3, the number 724,344 is divisible by 6. f) 8: The number formed by the last 3 digits is 344. Since 344 is divisible by 8, the number 724,344 is divisible by 8. g) 9: The sum of the digits of 724,344 is 24. Since 24 is not divisible by 9, the number 724,344 is not divisible by 9. h) 10: Since 724,344 does not end in 0, the number 724,344 is not divisible by 10. 7 Now try Exercise 27 Prime Factorization of a Number Every composite number can be expressed as a product of two or more prime numbers. The process of breaking a given composite number down into a product of prime numbers is called prime factorization . The prime factorization of 18 is 3 3 2. × ×
RkJQdWJsaXNoZXIy NjM5ODQ=