Finding Divisibility Rules for Large NumbersDate: 12/21/2000 at 00:31:35 From: David Subject: Seeking out divisibility rules Is there any way to systematically find divisibility rules for any number n, where n > 10? Date: 12/21/2000 at 11:40:03 From: Doctor Rob Subject: Re: Seeking out divisibility rules Thanks for writing to Ask Dr. Math, David. Yes, there is a way. First of all, factor n into its prime power divisors: n = p1^e1 * p2^e2 * ... * pr^er. A number is divisible by n if and only if it is divisible by each prime power in this expression. That reduces the problem to one where n is a prime power. A number is not divisible by a prime power p^e if it is not divisible by the prime p itself, so a necessary but not sufficient condition is divisibility by p. If the number is divisible by p, you can divide it out, and see if the quotient is divisible by p^(e-1). That will reduce the problem to one where n is a prime number p. One way to find a test for divisibility by p is to find the smallest multiple of p of the form x*10^k + 1 or x*10^k - 1, where x is very small (preferably one digit). Then the test is that N is divisible by p if and only if the number gotten from N by chopping off the last k digits, multiplying them by x, and subtracting (or adding, respectively) that product to the rest of N, is divisible by p. For example, if you want to test divisibility by 107, you might find that 107 is a factor of 1899999, so you can test for divisibility by chopping off the last five digits, multiplying that by 19, and adding that product from the rest of the digits of N. The result will be divisible by 107 if and only if the N is. You can continue this until the number has at most five digits, then you have to try dividing by 107 directly. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ Date: 12/21/2000 at 13:35:00 From: Doctor Greenie Subject: Re: Seeking out divisibility rules Yes, there is. I'm not sure I could provide a rigorous mathematical justification for the method, so I'll just demonstrate it for a few cases. The method for any given n is based on the pattern of remainders formed when successive powers of 10 are divided by n. The method is best demonstrated by examples; however, here is an attempt to put the method in words: To determine whether a number is divisible by n, proceed as follows: (1) Multiply each digit in the 10^i column by the remainder when 10^(i+1) is divided by n. (2) Add all the numbers obtained in step (1). (3) The original number is divisible by n if and only if the number obtained in step (2) is divisible by n Let's first use this method to derive the familiar divisibility rule for 3. We start by finding the remainders when successive powers of 10 are divided by 3, until a pattern is found: power of 10 remainder when divided by 3 ----------- --------------------------- 10^1 1 10^2 1 10^3 1 : : Here the pattern emerges immediately: every power of 10 leaves a remainder of 1 when divided by 3. The rule that comes out of this method is as follows: "a number is divisible by 3 if (and only if) the number (1*units digit + 1*tens digit + 1*hundreds digit + ...) is divisible by 3" This is equivalent to the familiar rule that a number is divisible by 3 if and only if the sum of its digits is divisible by 3. (This method quickly obtains the corresponding familiar rule for divisibility by 9, since every power of 10 also leaves a remainder of 1 when divided by 9.) Perhaps you are familiar with the divisibility rule for 11: find the sum of the digits in the odd-numbered locations and the sum of the digits in the even-numbered locations and take the difference; if the difference is divisible by 11, then the original number is. Let's see if we can develop that rule using this method: power of 10 remainder when divided by 11 ----------- ---------------------------- 10^1 10 10^2 1 10^3 10 10^4 1 10^5 10 : : We can use a "trick" here to simplify our divisibility rule a bit. Wherever the remainder upon dividing by 11 is 10, we can also say the "remainder" is -1. Then our table looks like this: power of 10 remainder when divided by 11 ----------- ----------------------------- 10^1 -1 10^2 1 10^3 -1 10^4 1 10^5 -1 : : And from this we can see how, using our method, we can get the familiar divisibility rule for 11. Now let's use the method to obtain a divisibility rule for 7. power of 10 remainder when divided by 7 ----------- --------------------------- 10^1 3 10^2 2 10^3 6 (or -1) 10^4 4 (or -3) 10^5 5 (or -2) 10^6 1 10^7 3 10^8 2 10^9 6 (or -1) : : Without trying to put the rule into words, let's use it in an example. The number 5497756005 is divisible by 7. We can show this is so using our divisibility rule as follows: (5*3)+(0*2)+(0*6)+(6*4)+(5*5)+(7*1)+(7*3)+(9*2)+(4*6)+(5*4) = 15 + 0 + 0 + 24 + 25 + 7 + 21 + 18 + 24 + 20 = 154 and 154 is divisible by 7, so 5497756005 is also. Note carefully how this sum of 154 was obtained. In the string of products that were added to get the total of 154, the first digit in each product is a digit of the number whose divisibility is being checked, starting with the units digit and moving left; and the second digit in each product is the remainder when successive powers of 10 are divided by 7, starting with 10^1 for the units digit. Here's another example, to find a divisibility rule for 13. power of 10 remainder when divided by 13 ----------- ---------------------------- 10^1 10 (or -3) 10^2 9 (or -4) 10^3 12 (or -1) 10^4 3 10^5 4 10^6 1 10^7 10 (or -3) 10^8 9 (or -4) 10^9 12 (or -1) : : The number 3266497 is divisible by 13. We can show this is so using our divisibility rule as follows: (7*10) + (9*9) + (4*12) + (6*3) + (6*4) + (2*1) + (3*10) = 70 + 81 + 48 + 18 + 24 + 2 + 30 = 273 and 273 is divisible by 13, so 3266497 is also. Or we could keep the numbers smaller by using the negative remainders: (7*-3) + (9*-4) + (4*-1) + (6*3) + (6*4) + (2*1) + (3*-3) = (-21) + (-36) + (-4) + 18 + 24 + 2 + (-9) = -26 It can be interesting to see what kinds of rules result from using this method on numbers for which we already have divisibility rules. Consider the rule which results for divisibility by 6: power of 10 remainder when divided by 6 ----------- --------------------------- 10^1 4 10^2 4 10^3 4 : : Here the divisibility rule says a number is divisible if 4 times the sum of all the digits is divisible by 6. This is equivalent to saying that it is divisible by 6 if twice the sum of the digits is divisible by 3. And that is equivalent to the divisibility rule you are probably familiar with - that a number is divisible by 6 if it is divisible by both 2 and 3. So... You CAN get divisibility rules for any number... but most of them are much harder to use than long division (or other hand methods). And in this day of calculators, the divisibility rules are useless except as a mathematical exercise. - Doctor Greenie, 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/