## Divisibility Rules and Prime Factorization

2 (Prime) | A number is divisible by 2 if its last digit is 0, 2, 4, 6, or 8. Any even number is divisible by 2 |

3 (Prime) | Add all of the digits composing the number. If the sum of the digits is divisible by 3, then so is the original number. Example: If the number is 564, add 5 + 6 + 4 = 15. The sum of the digits (15) is divisible by 3, so 564 is also divisible by 3. |

4 (Composite) | A number is divisible by 4 if the number formed by its last two digits is divisible by 4, or if the number ends in 00. Examples: The number 5748 is divisible by 4 because the number formed by its last two digits (48) is divisible by 4. The number 300 is divisible by 4 because it ends in 00. |

5 ( Prime) | A number is divisible by 5 if its last digit is 0 or 5. |

6 ( Composite) | A number is divisible by 6 if it is divisible by both 2 and 3 (see above). |

7 ( Prime) | Draw a vertical line between the tens’ and ones’ digits, so that there are now two “numbers.” Multiply the rightmost “number” by 5, and then add the leftmost “number” to the product. If the result is divisible by 7, then so is the original number. Example: For the number 182, write it as 18|2, giving the two “numbers” 18 and 2. Multiplying the second “number” (2) by 5 and adding the first “number” (18) gives (5 × 2) + 18 = 28. Since the result (28) is divisible by 7, then so is 182. (When testing for divisibility by 7, it may be easier just to use your calculator.) |

8 (Composite) | A number is divisible by 8 if the number formed by its last three digits is divisible by 8, or if the number ends in 000. Examples: The number 5840 is divisible by 8 because the number formed by its last three digits (840) is divisible by 8. The number 7000 is also divisible by 8; it ends in 000. |

9 ( Composite) | Add all of the digits composing the number. If the sum of the digits is divisible by 9, then so is the original number. Example: If the number is 576, add 5 + 7 + 6 = 18. The sum of the digits (18) is divisible by 9, so 576 is also divisible by 9. (Note that 9 is not prime!) |

10 ( Composite) | A number is divisible by 10 if its last digit is 0. |

11 ( Prime) | Add every other digit composing the number, starting with the leftmost digit, and obtain the sum. Then add the digits not used previously and obtain a second sum. Find the difference between the two sums. If this difference is 0 or is divisible by 11, then the original number is divisible by 11. Example: If the number is 1529, find the sum 1 + 2 = 3, then find the sum 5 + 9 = 14. The difference between the two sums is 14 – 3 = 11, which is divisible by 11, so 1529 is also divisible by 11. Can you show that the number 142,857 is also divisible by 11? |

12 (Composite) | A number is divisible by 12 if it is divisible by both 3 and 4 (see above). |

The first few primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,…

When factoring a large number, do not try every prime all the way up to the number. For example, if factoring 503, test each prime in order (2, 3, 5, 7, 11, 13, etc.) to see whether it is a factor of the large number. Before checking each prime (for example, before checking 13), take that prime and multiply it by itself (in this example, 13 × 13 = 169). If the product (169) exceeds the number to be factored (503), then you have gone far enough and may stop. In this example, it is necessary to go farther and test 17 (17 × 17 = 289) and 19 (19 × 19 = 361). Since the next prime (23) has the property that 23 × 23 = 529, which exceeds 503, we can stop after 19 (note that it is not necessary to test whether 23 is a factor of 503). Many students make the mistake of assuming that a large number is prime if it is not divisible by 2, 3, 5, and 7. Often you must do additional testing (beyond 7)! The procedure just described tells you exactly how far you must go when testing factors.