Divisibility rules

Some say "God created integers and the rest is human creation"

So with this beautiful thought let me show you how divisibility rules are constructed.

Let us start with 3.

Since childhood we have been mugging like parrots "add all digits of number and if that is divisible by three than the whole number is divisible by 3"

Let us see where this rule comes from.


We all know this simple fact.

Every number can be expressed as sum of coefficients multiplied by powers of 10

Say 1236 =1*10^3 +2*10^2+3*10^1+6*10^0

Now we can also express this as coefficients multiplied by powers of 100 instead of 10

Say 1236 =12*100^1+36*10^0

Similarly we can try pwers of 1000

Say 1*1000^1+236*1000^0

and so on

Now let us come back.So if we need to operate on digits of number, instead of number as one whole uint, we need to represent them like this in any of the forms as above.

say we have a number 1236 we can write it as 1*10^3 +2*10^2+3*10^1+6*10^0

now let us write as before 1236=1*10^3 +2*10^2+3*10^1+6*10^0= something (mod 3)

but we know this something should be equal to 0 if we this is number is divisible by 3 .

So let us evaluate the LHS and see whether indeed this is the case.

now let us see we have powers of 10 in LHS.

and we know how to find modulo of powers.

we start with 10.

Now 10=1 (mod 3) as 10 leaves remainder 1 when divided by 3
again 10^2 =10*10 = 1*1 =1 (mod 3) replace each 10 by 1 that is substituting from eqation above

Similarly 10^3=1*1*1 =1(mod 3)

So any power of 10 leaves remainder 1 when divided by 3.

Now lets us get back to 1*10^3 +2*10^2+3*10^1+6*10^0= something (mod 3)

replace each of the powers by 1

1+2+3+6=12 (mod 3)
12=0(mod 3)
so that something is indeed 0 and this number can be divided by 3

now let us write this all formally

let us have a number abcde... of n digits
where abcde.. are digits of number

then it can be written as a*10^(n-1)+b*10^(n-2)+c*10(n-3) and so on

In mod 3 we can have each term a*1+b*1+c*1+...=a+b+c... (mod 3)
So if a+b+c+... =0 (mod 3) then this number is divisible by 3 right
Thus if sum of digits is divisible by 3 the whole number is divisible by 3


Now if I tell you 10= -1 (mod 11). then can you derive the famous divisibility rule for 11.
(yes 11 goes 1 times and remainder is -1 . 10=1*11-1

you can also note that 10=10 (mod 11) subtracting 11 from RHS gives the same result.
Note you can substract any multiple of 11 from either side without changing the equality
Think why , any way you can always do a-b and see whether it is divisible by mod number n and find whether equation is correct)

You need to proceed identically that is finding modulo of powers of 10 wrt 11 mod.







Now let us try some other numbers.


Say 9.

Now we again know that 10 =1 (mod 9)

Yes same as 3

So we can have 10=1 (mod 9)
or 10^2 = 1*1 (mod 9)

and similarly 10^3=1*1*1 (mod 9)=1 (mod 9)

So any power of 10 is 1 (mod 9)

Again any number of form abc.... can be written as a*10^n +b*10^(n-1) and so on

So we can write abc...=a*10^n +b*10^(n-1)+....=a+b+c... (mod 9)
So if a+b+c+... =0 (mod 9) then umber is divisible by 9

Same as 3.If sum of digits is divisible by 9 then whole number is divisible by 9.

Similarly let us try 11.

for 11

we know 10=-1 (mod 11)
So 10^2=(-1)*(-1) replacing each 10 with -1
So 10^2 =1
again 10^3 =(-1)(-1)(-1)=-1 (mod 11)
and so on odd powers return -1 and even powers of 10 gives 1

So for a number abcd...
We can have abcd.....=a^(n)+b^(n-1)+c^(n-2)+d^(n-3) ...=a-b+c-d+....(mod 11)
So all we need to do is sum the alternate terms together and take the difference if that is divisible by 11 the whole number is divisible by 11
Note it is not important which number we start with and which sum we subtarct from which.
All we need to do is form the sum with alternate digits.

Say we get a-b+c-d+...= something (mod 11)
We can easily multiply by -1.Remember the rule we can always multiply with a constant.
and get -a+b-c+d ..= -something (mod 11)
Again that 'something' may be neagtive positive doesn't matter it is just that 11 should divide it.

With that let us become a bit adventurous and try for other numbers

Now let us try so where do we start.

We just saw that it is very convenient if powers of 10 leave remaninder 1 or -1 with some number N.Say if N is 3,11,9 we were quick to formulate the rule.

But we have already tried numbers which divide 11 and 9.Actually 11 is prime so we can't do much with it.

So 3 divides 9 so we have a rule for it .
9 and 11 are as such by default.

Now let us try 999,1001 both of these will leave remainder 1 and -1 respectively.

And fortunately this time.

1001 has factor 1001 =7*13*11 check it.


As always we try to find modulo of powers of 1000 this time instead of 10.

So we can have

1000 = -1 (mod 7) as 1000 =143*7 -1
1000=-1 (mod 13) similarly
1000=-1 (mod 11)

so 1000 leaves remainde -1 for each.

So what is the rule.

Proceed similarly.

let us take a number abcdef= abc*(1000^1) +def*(1000^0)=abc(1000)+def*1
that is expanding in powers of 1000
so we have abc*(1000^1) +def*(1000^0)=abc(1000)+def*1=abc(-1)+def (mod 7 or 13 or 11)
=abc-def (mod 7 or 13 or 11)
So rule is--- form two groups of number taking three digits aleternately at a time beginning from right .
Sum and take the difference of these two groups.
If this diiference is divisible then you can be sure whole number is divisible.
Let us check it
Say let us try 123898768
form the group 123, 898 ,768

Take the sum and subtract (123+768)-(898)=-7
and -7 is divisible by 7 .(You can reverse it also and get 7 as result instead doesn't matter.)
So this number is divisible by 7 check it.
So we have one more test for 11
and we have test for 13 and 7


you can try for 33
as 100 =1 (mod 33)

and may be even higher powers of 10.