Divisibility Rules

	Nearly everyone knows the obvious divisibility rules, such as for a number to be divisible by 3 its digits must add up to some multiple of 3.  However, some others aren’t as commonly known.  The purpose of this… whatever it is is to show you how to come up with a divisibility rule for any number.  Be warned, though, some of them aren’t too pretty.
	My method is a fairly easy-to-understand method (although I may not have explained it excellently) of finding the remainder of any division, really.

	Take a number, say 7.  You want to know the divisibility rule that lets you find multiples of 7.

First, find 1/7.  This is a repeating decimal, namely .142857142857142857…  This means that you are going to have to find a six-step sequence for the divisibility rule.  Don’t worry, I’ll get to what this means in a second.

Next, find the largest multiple of 7 smaller than each power of 10.  This is:
7	(10)
98	(100)
994	(1000)
9996	(10000)
99995			(100000)
999999			(1000000)
9999997			(10000000)
99999998		(100000000)
999999994		(1000000000)
9999999996		(10000000000)
99999999995		(100000000000)
999999999999		(1000000000000)
9999999999997		(10000000000000)

Did you notice how, after six of them, the sequence of ending digits repeated?  This corresponds to the fact that 1/7 repeats every six digits.  The same will be true of any number; the number of digits its reciprocal repeats in will be the number of steps.

Now, take a number, say 118.  You want to know if 118 is divisible by 7.  What do you do?  Well, 100 isn’t divisible by 7, that’s obvious.  However, 98 is.  So if 118 is divisible by 7, so is 118-98.  If 118 isn’t divisible by 7, then neither is 118-98.  As it happens, 118-98=20.  It should be fairly obvious that 20 isn’t divisible by 7, but let’s take this to the next step.  10 isn’t divisible by 7, but 7 is.  Since there are two 10s in 20, we can subtract 7 twice from 20 to get a number that is divisible by 7 if 20 is (and therefore 118 is), and isn’t divisible by 7 if 20 isn’t (and therefore 118 isn’t).  20-7*2=20-14=6.  6 is not divisible by 7; therefore 20 is not divisible by 7; therefore 118 is not divisible by 7.  Was that so hard?

Take a bigger number, say 1234567890.  We’re going to do essentially the same thing to it, but I want to generalize the process a bit first.  In the earlier example, we subtracted 98 from 118, getting 20.  Isn’t this the same as having 118, taking off the first digit: 1  18, and adding that first digit * 2 to the remaining number: 1*2=2; 18+2=20.  It is.  Similarly, when we had 20, we took off the first digit:  2  0, multiplied that first digit by 3:  2*3=6, and added that to the last number: 0+6=6.  This is because 10-7=3, and 100-98=2; essentially you can say that 10/7 has a remainder of 3, and 100/7 has a remainder of 2, and all we want to do is count the remainder; if we can get it to some number divisible by 7, then there really is no remainder, and the whole number is divisible by 7.  If there is some remainder, then we will find it, and we can conclude that the whole number is not divisible by 7.  118 has a remainder of 6 (112 is divisible by 7), the number that we found.
	So take 1234567890.  I propose that we can line it up like so:
1	2	3	4	5	6	7	8	9	0
c	b	a	f	e	d	c	b	a	x

where for every unit in a we add 3 to the entire number, for every unit in b we add 2 to the entire number, for every unit in c we add 6, for every d add 4, for every e add 5, and for every f add 1.  (We skip what I have marked as x because there is no multiple of 7 lesser than 1.  Later on, you will skip two digits if finding the multiples of two-digit numbers, three digits for three-digit numbers, and so on.  This should not cause any major problems.)
Let’s try it.
1	234567890
1*6 = 6
234567890+6=234567896

2	34567896
2*2 = 4
34567896+4=34567900

3	4567900
3*3 = 9
4567900+9=4567909

4	567909
4*1 = 4
567909+4=567913

5	67913
5*5=25
67913+25=67938

6	7938
6*4=24
7938+24=7962

7	962
7*6 = 42
962+42=1004

1	004
1*6 = 6
4+6=10

1	0
1*3 = 3
0+3=3

And, indeed, the remainder of 1234567890/7 is 3.

Take another example, one where the remainder is 0.  7*654782391 (a random example) is 4583476737.

4	5	8	3	4	7	6	7	3	7
c	b	a	f	e	d	c	b	a	x
a=3, b=2, c=6, d=4, e=5, f=1

4	583476737
4*6=24;		583476737+24=583476761
5	83476761
5*2=10;		83476761+10=83476771
8	3476771
8*3=24;		3476771+24=3476795
3	476795
3*1=3;		476795+3=476798
4	76798
4*5=20;		76795+20=76818
7	6818
	7*4=28;		6818+28=6846
6	846
	6*6=36;		846+36=882
8	82
8*2=16;		82+16=98
9	8
9*3=27;		27+8=35
3	5
3*3=9;		5+9=14
1	4
1*3=3;		4+3=7

Obviously, at some point it becomes obvious whether or not the number is divisible by 7.  Careful… it’s incredibly easy to make arithmetic mistakes here.

But what if you want to find divisibility rules for other variables?  Let’s take 4 as an easy example.
Take the largest multiples of 4 smaller than the powers of 10.
8			(10)
100			(100)
1000			(1000)
10000			(10000)

	and so on.  Obviously, if 100 is divisible by 4, so is 1000 (=10*100).  So use the strategy from before.  For every 10 that you subtract, add 2 (so net you’re only subtracting 8, a number divisible by 4).  Since 100 and all the greater powers of 10 are divisible by 4, you needn’t worry about them!  So, take 1234567890 again.  Is it divisible by 4?

1	2	3	4	5	6	7	8	9	0
0	0	0	0	0	0	0	0	a	x
a=2

9	0
9*2=18;		0+18=18
1	8
1*2=2;		8+2=10
1	0
1*2=2;		0+2=2

Just as it says, the remainder of 1234567890/4 is 2.

Take a harder number, like 13.  Do the same thing.  Note that since 1/13=.769230769230…, you’ll have to find the first six digits.
91			(100)
988			(1000)
9997			(10000)
99996			(100000)
999999			(1000000)
9999990			(10000000)

So, for any number written edcbafedcbafedcbafedcbaxx, multiply a by 9 (100-91), b by 12 (1000-988), c by 3, d by 4, e by 1, and f by 0, and add to xx.  That’s all there is to it.