Thursday, 13 June 2013

Number Theory Divisibility Methods

For checking divisibility by any 'prime/odd' number except for factors of 5', you have the concept of base number.

Number. Add Base Number Subtract Base Number

3: 1 2
7: 5 2
9: 1 8
11: 10 1
13: 4 9
17: 12 5
19: 2 17
21: 19 2
23: 7 ?
27: ? 8
29: 3 ?
...
...
And so on.... A method to get these 
described below 

Now for checking divisibility either add the last digit x add base number to the number "formed by removing last digit" or you can subtract last digit x subtract base number from the "formed by removing last digit"

e.g for check for 51/17 either 5- 1*5 =0 or 5 + 1*12 =17 hence divisible.
to check 312/13 we can 31+2*4 =39 hence dvisible or we can 31-2*9 = 13 ence divisible.
to check 61731/19 = 6173 + 1*2 = 6175 = 617 + 5*2 = 627 = 62 + 7*2 = 76 hence divisible.
to check 357976/29 = 35797 + 6*3 = 35815 = 3581 +5*3 = 3596 = 359 + 6*3 = 377 = 37 + 7*3 = 58 hence divisible..
to check 382294/11 = 38229-4*1 =38225 = 3822-5 = 3817 = 381 - 7 = 374 = 37 -4 =33 Hence divisible..


The SubractbaseNumber for a number can be obtained as the {(samllest multiple of number which ends in one)-1}/10
i.e. for 3 or 7 it is (21-1)/10 =2
for 13 it is 91-1/10 = 9.


The AddbaseNumber for a number can be obtained as the {(samllest multiple of number which ends in nine)+1}/10
i.e. for 13 it is (39+1)/10 =4.
for 7 it is 49+1/10 = 5

Proof:
For SubtactBaseNumber say the number abcde...
I want to check divisibility by 17 where subtractbasenumber is 5

I can always write abcde... as 10X+Y (where Y is last digit and X is number formed by removing last digit)

Now X-Y*5 = (10X -50Y)/10 = (10X + Y -51Y)/10 = (OriginalNumber - 51 Y ) / 10

The number '51 Y' is a multiple of 17 so if "OriginalNumber" is divisible by 17 then "OriginalNumber - 51*Y" got to be.. i.e. "10X - 50Y"
as 10 and 17 are co-prime if "10X- 50Y" is divisible the "X-5Y" got to be.....

same theory hold's for addbasenumbers too....

This also defines why it is so easy to check divisibility by 3 or 9 just keep on adding the digits...

And you can check divisibility by 11 just by keeping on subrating digits form previous number.. (which is same as taking sum of even/odd location separately..)
Divisibility by 7
Only for those interested in Number theory (Not a Cat short-cut)

say the number is :
38,391,787

Separate into pairs of digits
38 39 17 87

Consider the difference between each pair of digits and the nearest multiple of seven, beginning for the first pair at right, lower (upper) for the first, upper (lower) for the second and so on, alternating for each new pair.

4 -----4 (21-17)
38 39 17 87
---4 ------3 (87-84)

The resulting digits, read from right are 3444 (which is also a number multiple of 7).
Proceed in the same way with 3,444

1
34 44
----2

The final pair 21 is a multiple of seven, so is the original number 38,391,787.

ANOTHER EXAMPLE
Look how fast this method is.
Consider the 15-digit number 531,898,839,909,822
2 ----2--- 3 ----0
5 31 89 88 39 90 98 22
---3 ---4 ----6 ----1

Now we have 10,634,232
4 -----0
10 63 42 32
----0 ----4

And now 4,004

2
40 04
---4

Which gives 42, a multiple of 7.
We only need three steps for a 15-digit number.
This is called TOJA's method of divisibility. Incidentally this also works for 11 and 13. Just a little manupulation is required, (in case you get a remainder of more than 9)

Let A = 5,962
7
59 62
à 77 which is a multiple of 1
--7

EXAMPLE 2
Let A = 5, 971,845

6---- 4
5 97 18 45
à
--9 ----1

8
14 96 -> 88 ->divisible
----8

EXAMPLE 3
Let A = 80,714,546

8 ----10
80 71 45 46
----5
-------2

The resulting numbers ( 2 10 5 8 ) don’t form a decimal number, so proceed in this way: Put the exceeding number 1 from 10, below the 2 and sum.

2
0 5 8 -> 3 0 5 8
1

3
30 58
à 33
---3


THE TOJA’S METHOD FOR DIVISIBILITY BY 13

EXAMPLE 1
Let A = 7, 046

8 (78 – 70)
70 46
à
78 which is a multiple of 13
---7 (46 – 39)


EXAMPLE 2

Let A = 9,581,681,629

----10 ----10
95 81 68 16 29
4-------3 ------3

--9
4 04 04
3 ----4

9
4 94 -> 39 divisible
--3