Divisibility Rule for All DivisorsDate: 11/07/1999 at 22:13:17 From: Jonathan Y Chung Subject: Number Theory I heard from a friend that there exists a theorem that you can use to figure out divisibility rules for all natural numbers. Is there such a theorem? If it exists, could you tell me the name of it? Thanks, Jonathan Date: 12/31/1999 at 09:01:38 From: Doctor TWE Subject: Re: Number Theory Hi Jonathan, I don't know of a specific theorem, but I have made some observations about the divisibility rules. All the divisibility rules deal with the relation of the divisor number and 10. Let's look at some examples: 2 and 5: Since these are divisors of 10, all multiples of 10 are divisible and you only have to check the last digit. 4, 8, 16, ... and 25, 125, 625, ...: These are powers of 2 (4 = 2^2, 8 = 2^3, etc.) and powers of 5 (25 = 5^2, 125 = 5^3, etc.) Since each power of 10 is divisible by the same power of 2 or 5, we only have to check the last n digits (where n is the power of 2 or 5.) For example, to see if a number is divisible by 8 (8 = 2^3) we check to see if the last three digits are divisible by 8. Likewise, to see if a number is divisible by 25 (25 = 5^2) we only have to check whether the last two digits are divisible by 25. 3 and 9: 10 divides by 3 or 9 with a remainder of 1 (we call it "modulo 1"). So every multiple of 10 has a remainder of 1. Likewise 100 is 99+1, 1000 is 999+1, etc. We can "cast out" the 9's, 99's, 999's etc. and just count the "remainder 1's." That's why you just add up the digits. Every digit is the number of "remainder 1's." 7: There are two alternate methods; one follows the pattern I'm building up to. That method is as follows: beginning with the leftmost digit, take the total, triple it, and add the next digit. For example, with 1834 we'd start with 1*3 = 3, then add 3+8 = 11, triple that for 11*3 = 33, then add 33+3 = 36, triple that for 36*3 = 108, then add 108+4 = 112. If we weren't sure that 112 was divisible by 7 we could repeat the process: 1*3 = 3, 3+1 = 4, 4*3 = 12, 12+2 = 14. (We should recognize that 14 is divisible by 7.) Why does this work? Because 10 = 7+3. So for each 10 we have in the number, we can "cast out" 7 and keep the "remainder 3," which we add to the ones digit. For multiples of 10, we have to keep each "remainder 3," which is why we multiply by 3. 100 is 70 + 30, so for each 100 we "cast out" 70 and add each "remainder 30" as +3 to the tens digit (again, we need to multiply the hundreds digit by 3 to account for every "remainder 30" we had). 11: For 11, we alternately add and subtract digits from left to right. Why? Because 10 = 11 - 1. Every 10 is one short of an 11, so we subtract 1 for each group of ten from the units. If we have hundreds, we subtract 1 for each group of 100 from the tens, etc. Technically, this means we should start by subtracting the leftmost digit, then adding the next, etc., but it doesn't matter in this case. The answer will have the same magnitude, just the opposite sign. To formalize this (and make it fit with the generalization I'm leading up to), we begin with the leftmost digit, multiply the total by -1, then add the next digit; repeating until we get to the units digit. If the result is a multiple of 11 (positive, negative or zero), so was the original number. 13: Since 10 = 13-3, we can start with the leftmost digit, multiply the total by -3, and add the next digit. For example, for 1859 we get: 1*(-3) = -3, -3+8 = 5, 5*(-3) = -15, -15+5 = -10, -10*(-3) = 30, 30+9 = 39; which is a multiple of 13, so 1859 is a multiple of 13. As with 7, there are other methods that I'm overlooking because they don't fit the generalization below. 6, 12, 14, 15, etc.: Since these are composite numbers, we just have to check for divisibility by all of their factors (2 and 3 for 6, 4 and 3 for 12, 2 and 7 for 14, etc.) Looking at 7, 9, 11 and 13, we can develop a general rule as follows: First, determine the "multiplier" (call it m) by subtracting the divisor from 10. Next, beginning with the leftmost digit, multiply the total by m and add the next digit (from left to right) until all digits have been added. If the result is divisible by the divisor, so was the original number. Let's try this with a test case. Suppose we wanted to see whether 715343 is divisible by 17. First, we let m = 10 - 17 = -7. Then we apply the rule from left to right (to save space, I'll do each multiply-and-add in one step): 7*(-7)+1 = -48 -48*(-7)+5 = 341 341*(-7)+3 = -2384 -2384*(-7)+4 = 16692 16692*(-7)+3 = -116841 But is -116841 divisible by 17? We'll apply the rule again to this result. We can ignore the (-) at the beginning (if -x is divisible by y, so is x divisible by y): 1*(-7)+1 = -6 -6*(-7)+6 = 48 48*(-7)+8 = -328 -328*(-7)+4 = 2300 2300*(-7)+1 = -16099 Here we go again. See whether 16099 is divisible by 17: 1*(-7)+6 = -1 -1*(-7)+0 = 7 7*(-7)+9 = -40 -40*(-7)+9 = 289 If we don't know that 289 = 17^2, we can apply the rule one more time: 2*(-7)+8 = -6 -6*(-7)+9 = 51 which is 17*3. So our rule says that 715343 IS divisible by 17. Checking by calculator, 715343/17 = 42079 exactly. As you can see, when our multiplier is close to 10, it doesn't reduce the number much, and we have to repeat the process many times before we get something reasonable to check by hand. This rule won't work with divisors larger than 20 because the magnitude of the multiplier would be larger than 10, so we'd be making larger numbers to check instead of smaller ones. Can you see a way to extend the generalized rule for divisors larger than 20? To see why other divisibility methods work, check out Divisibility Rules from the Dr. Math FAQ and our Math Tips and Tricks page: http://mathforum.org/dr.math/faq/faq.divisibility.html http://mathforum.org/k12/mathtips/division.tips.html#divide13 - Doctor TWE, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/