Divisibility Tests in Different BasesDate: 11/16/2008 at 03:52:20 From: Mia Subject: Divisibility tests in different base-systems How do I determine the divisibility test for 7 in the base-nine system? So far, I created a multiplication chart for base-nine and found that compared to the base-ten system, its Base 10 Base 9 7 7 14 15 21 23 28 31 35 38 42 46 49 54 56 62 63 70 and notice that the number in the base 9 column increased by 1 except the fourth and fifth numbers. I also divided the numbers because I was also looking for a divisibility test for 3. So, now I have no idea how to find the test for 7. Date: 11/17/2008 at 00:23:39 From: Doctor Greenie Subject: Re: Divisibility tests in different base-systems Hi, Mia -- A very interesting question! In preparing an answer, I have learned a lot more than I previously knew about divisibility rules (and I thought I knew a lot before this...!) This answer will be quite lengthy, showing three algorithms of very different types for testing for divisibility by 7. For a better understanding of the three different algorithms, we will first look at them with a base 10 number; then we will tackle the algorithms in base 9. For my demonstrations I will use the following number which is divisible by 7: 3929625 (base 10) = 7348380 (base 9) I will provide references in the Dr. Math archives for all three of the algorithms I discuss. Consult those references if you have any questions about the contents of my message. I-a. The first algorithm; in base 10.... For this first algorithm, I provide the following reference in the Dr. Math archives: Finding Divisibility Rules for Large Numbers http://mathforum.org/library/drmath/view/55962.html This method uses the values of powers of 10, modulo 7, to create a numerical expression from the given number; the given number is divisible by 7 if and only if the simplified expression is divisible by 7. The powers of 10, modulo 7, form the following repeating sequence: 3, 2, -1, -3, -2, 1, (repeat...) The expression we build, using these modulo 7 numbers and the digits of the original number--as explained on the referenced page--is 5(3) + 2(2) + 6(-1) + 9(-3) + 2(-2) + 9(1) + 3(3) This expression simplified is 15 + 4 - 6 - 27 - 4 + 9 + 9 = 0 Because 0 is divisible by 7, the original number is divisible by 7. General comments on this first method when in base 10: (1) It seems a bit like magic; it is difficult to understand why it works. (2) It is slow, with a great deal of sometimes difficult computation required--determining the repeating sequence of values of the powers of 10 modulo 7; and then forming and simplifying the long expression using those values and the digits of the given number.... II-a. The second algorithm, in base 10.... For this second algorithm, I provide the following reference in the Dr. Math archives: Divisibility Tests to 50 and Beyond http://mathforum.org/dr.math/faq/faq.divisibleto50.html (For any attempt to understand how this algorithm (in two varieties) is derived, refer to the given reference.) To begin using this algorithm, we find the smallest integer m for which 10m-1 is divisible by 7; we find it to be m = 5. Then the algorithm for testing for divisibility by 7 in base 10 is 1. remove the last digit of the number, multiply it by 5, and add it to the number that remains; 2. repeat as necessary until the remaining number is recognizable as being divisible by 7 I hope you can follow the calculations below that demonstrate that my example base 10 number is divisible by 7, using this algorithm: Remember my original base 10 number is 3929625. Using this second algorithm, we find 3929625 (remove 5, multiply it by 5, and add to remaining #) + 25 ------ 392987 (remove 7, multiply it by 5, and add to remaining #) + 35 ----- 39333 + 15 ---- 3948 + 40 ---- 434 + 20 ---- 63 We know that 63 is divisible by 7; that means our original number is also divisible by 7. With the other version of this algorithm, instead of multiplying the last digit by 5 and adding, we multiply it by 2 (because 7-5=2--see the referenced page in the archives) and subtract. Here is this alternative form of this second algorithm to again show my example number is divisible by 7: 3929625 (remove 5, multiply it by 2, and subtract from #) - 10 ------ 392952 (remove 2, multiply it by 2, and subtract from #) - 4 ----- 39291 - 2 ---- 3927 - 14 --- 378 - 16 -- 21 We know that 21 is divisible by 7; that means our original number is also divisible by 7. General comments on this second method when in base 10: (1) It too seems like magic, since it is difficult to understand why it works. (2) On the other hand, with a little practice, the actual use of the process requires calculations that are far easier than with the first algorithm. III-a. The third algorithm, in base 10.... For this third algorithm, I provide the following reference in the Dr. Math archives: Divisibility Algorithm http://mathforum.org/library/drmath/view/58516.html This algorithm really does not require a reference. It is easy to explain the method; and it is easy to understand why the method works. With this method, we simply add or subtract multiples of our divisor to the number we are working with to obtain trailing zeros, and then we simply drop those trailing zeros, since trailing zeros don't affect the divisibility of a number. Here is a demonstration of the use of this third algorithm to verify that our example number is divisible by 7: 3929625 + 35 = 3929660 --> 392966 392966 + 14 = 392980 --> 39298 39298 - 28 = 39270 --> 3927 3927 - 7 = 3920 --> 392 392 + 28 = 420 --> 42 We know 42 is divisible by 7, so our original number is divisible by 7. General comments on this third method when in base 10: (1) It is easy to understand why it works. (2) The actual steps required are far easier than either of the other methods. (3) The calculations required are far easier than either of the other methods. NOW.... Let's look at these three different algorithms for checking for the divisibility of a number by 7 if we are working in base 9.... Remember that my example number, 3929625 in base 10, is 7348380 in base 9.... I-b. The first algorithm; in base 9.... Because we are now in base 9, this method is going to be based on the values of the powers of 9, modulo 7 (not values of the powers of 10, modulo 7). In base 9, the powers of 9, modulo 7, form the following repeating sequence: 2, 4, 1, (repeat...) The expression we build, using these modulo 7 numbers and the digits of the original number--as explained on the referenced page--is 0(2) + 8(4) + 3(1) + 8(2) + 4(4) + 3(1) + 7(2) This expression simplified is 0 + 32 + 3 + 16 + 16 + 3 + 14 = 84 Because 84 is divisible by 7, the original number is divisible by 7. General comments on this first method when in base 9: (1) It still seems a bit like magic; it is difficult to understand why it works. (2) It is slow, with a great deal of sometimes difficult computation required--determining the repeating sequence of values of the powers of 9 modulo 7; and then forming the long expression using those values and the digits of the given number.... (3) On the other hand, all the actual calculations for this method are performed in base 10. II-b. The second algorithm, in base 9.... Similar to when working in base 10, to begin using this algorithm in base 9, we find the smallest integer m for which 9m-1 (not "10m-1") is divisible by 7; we find m=4. Then the algorithm for testing for divisibility by 7 in base 10 is 1. remove the last digit of the number, multiply it by 4, and add it to the number that remains; 2. repeat as necessary until the remaining number is recognizable as being divisible by 7 Again I hope you can follow the calculations below that demonstrate that my example base 9 number is divisible by 7, using this algorithm. The process is complicated by the fact that we are now performing arithmetic (addition or subtraction) in base 9. Remember my original base 9 number is 7348380. Using this second algorithm, and doing our arithmetic in base 9, we find 7348380 (remove 0, multiply it by 4, add to remaining #) + 0 ------ 734838 (remove 8, multiply it by 4, convert 32 to 35 in + 35 base 9, add to remaining #) ----- 73528 + 35 ---- 7387 + 31 --- 770 + 0 -- 77 + 31 -- 38 We have had to perform single-digit base 9 multiplication and base 9 addition to get to this point; now we have to do some evaluation of the number "38" base 9 to see if it is divisible by 7. "38" base 9, converted to base 10, is 3(9) + 8(1) = 35, which is divisible by 7. So we know that 38 (base 9) is divisible by 7; that means our original number is also divisible by 7. With the other version of this algorithm, instead of multiplying the last digit by 4 and adding, we multiply it by 3 (because 7-4=3--see the referenced page in the archives) and subtract. Here is this alternative form of this second algorithm to again show my example number is divisible by 7: 7348380 - 0 ------ 734838 (remove 8, multiply by 3, turn 24 into 26 in base - 26 (nine, subtract from remaining #) ----- 73456 - 20 ---- 7325 - 16 --- 715 - 16 -- 54 This number, 54 in base 9, converted to base 10 is 5(9) + 4(1) = 49. We know that 49 is divisible by 7; that means our original number is also divisible by 7. General comments on this second method when in base 9: (1) It too still seems like magic, since it is difficult to understand why it works. (2) The actual calculations required are HARDER when in base 9, because we need to perform multiplication and addition (or, even worse, subtraction) in base 9 with this method. III-b. The third algorithm, in base 9.... As when in base 10, with this method, we simply add or subtract multiples of our divisor to the number we are working with to obtain trailing zeros, and then we simply drop those trailing zeros, since trailing zeros don't affect the divisibility of a number. But now the arithmetic must be performed in base 9.... Following is a demonstration of the use of this third algorithm to verify that our example number is divisible by 7. We will need (for quick reference) the list of multiples of 7 you found for base 9: 7*1 = 7 7*2 = 15 7*3 = 23 7*4 = 31 7*5 = 38 7*6 = 46 7*7 = 54 7*8 = 62 7348380 --> 734838 734838 + 31 = 734870 --> 73487 73487 + 62 = 73550 --> 7356 7356 + 23 = 7380 --> 738 738 + 31 = 770 --> 77 77 + 62 = 150 --> 15 From our list of multiples of 7, we know 15 (base 9) is divisible by 7, so our original number is divisible by 7. General comments on this third method when in base 10: (1) It is easy to understand why it works. (2) The actual steps required are far easier than either of the other methods. (3) The calculations required must be performed in base 9; overall, however, this third method is still much easier than the first method. I hope at least some of all this is understandable to you. I have long held the opinion that the third method described above is far more practical than either of the other methods when in base 10. Having now investigated--in response to your question--methods for testing divisibility in other bases, I firmly believe that the third method is far more practical in any base. Another advantage of the third method, not seen in the above discussion since I was only addressing divisibility by a single number (7), is that it can easily be applied for ANY divisor--whereas for each of the other methods the details of the process are completely different for different divisors. - 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- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/