Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For denominators like 13, 17 i often see my professor use a method to test whether a given number is divisible or not. The method is not the following : Ex for 17 : subtract 5 times the last digit from the original number, the resultant number should be divisible by 17 etc...

The method is similar to divisibility of 11. He calls it as compartmentalization method. Here it goes.

rule For 17 :

take 8 digits at a time(sun of digits at odd places taken 8 at a time - sum of digits at even places taken 8 at a time)

For Ex : $9876543298765432..... 80$digits - test this is divisible by 17 or not.

There will be equal number of groups (of 8 digits taken at a time) at odd and even places. Therefore the given number is divisible by 17- Explanation.

The number 8 above differs based on the denominator he is considering.

I am not able to understand the method and logic both. Kindly clarify.

Also for other numbers like $13$ and $19$, what is the number of digits i should take at a time? In case my question is not clear, please let me know.

share|improve this question
    
I cannot figure out the rule. What are the "blocks of 8 digits at even/odd places"? For example, given the number 1234567890123456, what would the two blocks look like? –  celtschk Aug 20 '12 at 15:27
    
I think he means the two 8 digit numbers formed by every other digit, in this case $13579135$ and $24680246$. –  axblount Aug 20 '12 at 15:38
    
@celtschk: you split into blocks of 8 starting from the ones digit, so the first block would be $90123456$, the second would be $12345678$. Then we have $1234567890123456 \equiv 90123456-12345678 \pmod {17}$ –  Ross Millikan Aug 20 '12 at 15:49
add comment

4 Answers

The Similar can also be said for divisibility by $13$

$10^3/13$ gives a remainder of $-1$
$10^6/13$ gievs a remainder of $+1$

So again the rule for $13$, will be same as the rule for $7, 11$. Group the numbers into triplets as we see alternate changes of $-1$ to $+1$ between every three powers of $10$. So the rule for $13$ will also be

(Sum of triplets at odd places - Sum of triplets at even places) or Sum of digits at odd places taken $3$ at a time - Sum of digits at even places taken three at a time)

As i said, all this can be summarised as:

$10^x/B = +1$ holds for divisors (values of B) like $3,9, 37$

$10^x/B = -1$ and $+1$ for divisiors (values of B) like $7, 11, 13, 17$

$10^x/B = 0$ for divisors (values of B) like powers of $2$ and $5$

where $+1,0,-1$ are the remainders of the respective divisions

share|improve this answer
add comment

The whole process can be explained by writing

A^x/B = C where C can be +1 or -1 or 0. Here C is the remainder got on division of A^x by B.

Now we operate on base 10. So A takes a value of 10. B is the divisor for which you are attempting to set up a rule for. This method is called compartmentalisation. It is used to check on divisibility / remainder for numbers as you had stated .. not for the normal smal numbers. There are much effective rules for the same.

Suppose you talk of divisibility by 9: Consider any 2 digit number AB. This can be represented in terms of der place values as

AB = 10A+B = 9A+A+B.

Now if you were to check divisibility by 9.

[9A + (A+B)]/9. Then the first term 9A is divisible. Now if the whole number is to be divisible, we would want the terms (A+B) to also be divisible. So the divisibility of the number depends on (A+B) which is nothing but the digit sum. Which is why you see that the divisibility rule for 9 is "The digit sum of the number must be divisible by 9" Also you got to note that: 10^x/9 = +1 for whatever be the value of x. This results in another rule: 10^x/3 = +1 which is the rule for divisibility by 3.

Now consider the RULE FOR 7 A^x/B= C

Here A=10 (base 10), B = 7. Now we have to choose values for x such that it gives a remainder of C= +1 or -1.

we see the following pattern: 10^0/7 = +1

10^3/7 = -1

10^6/7 = +1

So we see that +1 and -1 remainders alternate every three powers of ten. This gives our compartmentalisation rule. The given number from left to right has to be grouped in threes and the rule of +1 and -1 for every triplet has to be applied. You will see it :

ABCPQRXYZ be a number. To check the divisibility by 7, we write it as:

[10^6 ABC]/7 + [10^3 PQR]/7 + [10^0 XYZ]/7

Now 10^6/7=+1 , 10^3/7 = -1 and so on.. This reduces to

(1xABC) (-1XPQR) (1*XYZ)

RULE : Sum of triplets at odd places - sum of triplets at even places

eg: 100200140240 /7 . What would be the remainder?

100 | 200 | 140 | 240 |

-1 | +1 | -1 | +1

  • 100- 140 = -240

200 + 240 = 440

You get 440-240 = 200

200/7 gives a R= 4

Now consider the RULE FOR 11 10^0 / 11 = +1 10^1/ 11 = -1 10^2/ 11 = +1 10^3/11 = - 1

FOr 11, you can do it in 2 ways. One is that you notice that every alternate power of 10 divided by 11 gives an alternating pattern of +1 and -1. So the compartmentalisation will now be for every digit. So you do a

Sum of digits at odd places - Sum of digits at even places.

But if you did notice the fact that 10^0/11 = +1 and 10^3/11 = -1 Then you will notice that 11, same as 7, has +1 and -1 alternating for triplets. So, you can proceed compartmentalising the number into triplets and doing the same thing as we did for 7.

Sum of triplets at odd places - Sum of triplets at even places.

So we see that so far : 1. 10^x / B = +1 will hold good for three cases i guess (not sure it may be more ... ) They are 3, 9 , 37.

Even 10^3/37 = +1 . So here there are no alternate +1 and -1 as 10^6/37 will also be +1. Note that (a^m)^n = a^mn

**Rule for 37 would be : Group the number into triplets and apply a +1 to each triplet.

  1. 10^x / B = +1 or -1 will hold good for 7, 11, 17 Rule for 17 (thus) : 10^8/17 = -1. So, 10^16/17 would be +1. So it becomes like (Sum of digits at odd places taken 8 at a time - sum of digits at even places taken 8 at a time. )**

    3. Also 10^x/B = 0 (gives a remainder of 0 )when B are powers of 2 or powers of 5.

I still dont know if it is possibile to cover all primes (atleast 2 digits) in this method. Perhaps you may have to use other techniques like Chinese Remainder Theorem or the Basic Remainder Theorem and so on.. That is because I still dont see any patterns for 23 and many more numbers. If anybody could add anything more to this .. it would be great.

Hope this post helps.

Cheers :)

share|improve this answer
add comment

Your professor is using the fact that $100000001=10^8+1$ is divisible by $17$. Given for example your $80$-digit number, you can subtract $98765432\cdot 100000001=9876543298765432$, which will leave zeros in the last $16$ places. Slash the zeros, and repeat. After $5$ times you are left with the number $0$, which is divisible by $17$, and hence your $80$-digit number must also be divisible by $17$.

When checking for divisibility by $17$, you can also subtract multiples of $102=6\cdot 17$ in the same way.

For divisibility by $7$, $11$, or $13$, you can subtract any multiple of the number $1001=7\cdot 11\cdot 13$ without affecting divisibility by these three numbers. For example, $6017-6\cdot 1001=11$, so $6017$ is divisible by $11$, but not by $7$ or $13$.

For divisibility by $19$, you can use the number $1000000001=10^9+1=7\cdot 11\cdot 13\cdot 19\cdot 52579$. By subtracting multiples of this number, you will be left with a number of at most $9$ digits, which you can test for divisibility by $19$ by performing the division.

share|improve this answer
add comment

You quote two different rules with different results. When testing for divisibility by 17 by subtracting 5 times the last digit from the orignal number without its last digit, you are using the fact that $51$ is divisible by $17$, so $10a+b \equiv 10a-50b \pmod {17}$, then the fact that $10(a-5b)$ is a multiple of $17$ if and only if $(a-5b)$ is. Unless you do further computation, you lose the remainder if the original number is not a multiple.

When you take blocks of 8 digits, you use the fact that $10^8+1 \equiv 0 \pmod {17}$, so $10^8a+b \equiv b-a \pmod {17}$ You retain the remainder in this case. For 13, you need half the period of its repeating decimal, which is 6, so you use blocks of 3. Note that $10^3+1=1001 \equiv 0 \pmod {13}$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.