What are the tests to see if a number is divisible by 2, 3, 4, ...

The question was asked by Brian Reese <brianr@phred.UUCP>, who
remembered the rules for 2 (the number is even), 3 (the sum of the
digits is divisible by 3; the sum can be taken repeatedly), 5 (the
number ends in 0 or 5) and 9 (the sum of the digits is divisible by 9),
but not those for 4, 6, 7 and 8.

Divisibility tests for various numbers.

2: Last digit is even (0,2,4,6,8)

3: Sum of digits is divisible by 3. Repeat if necessary, i.e. add
digits and then add digits of sum and so on.

4: Last 2 digits divisible by 4.

5: Last digit is 5 or 0

6: Divisible by both 3 and 2

7: This one is least intuitive. Take first digit, triple it. add
second digit, triple sum. and so on, finally adding last digit. if
this result is divisible by 7 so was the original number

Example, 126. take 1 triple to get 3 add 2 to get 5 triple to get 15
add 6 get 21 which is divisible. These additions and multiplications
can be done mod 7.

8: last 3 digits divisible by 8

9: Sum of digits is divisible by 9

10: last digit is zero.

11: add numbers in even places and subtract those in odd. Example 319
3 - 1 + 9 = 11 so 319 is divisible.

12: divisible by 3 and 4

13: same as seven but instead of tripling and adding, multiply by -3
and add.

14. divisible by 7 and 2

15. divisible by 3 and 5

16. last 4 digits divisible by 16

17. Very Messy.

All of these can be proved inductively. 7 and 13 look awkward, but if
done modulo these numbers are manageable. Actually all numbers around
10 can be done in that fashion. Multiply the sums by (10-x) if
checking for modulo x. 9 and 11 are simply done as special cases
because 10-9 = 1 and 10-11 = -1 and 11 is altered slightly by adding
the next digit multiplied by -1 a given power rather than multiplying
the sum.

Question. How do these tests change in different numbering systems?

-- Randolph Finder <rf1n+@andrew.cmu.edu>

Take a look at the following reference:
Lindsay Childs, "A Concrete Introduction to Higher Algebra", Springer-Verlag,
Corrected second edition, 1984, chapters 5 and 6.

-- William F. Hammond <wfh58@leah.albany.edu>

Minor simplifications:

> 4: Last 2 digits divisible by 4.

Last digit plus twice the tens digit is divisible by 4.

> 8: last 3 digits divisible by 8

Last digit plus twice the tens digit plus four times the hundreds digit is
divisible by 8.

> 16. last 4 digits divisible by 16

Last digit plus twice the tens digit plus four times the hundreds digit
plus eight times the thousands digit is divisible by 16.

Do we sense a pattern? :-)

> Question. How do these tests change in different numbering systems?

I leave this one to people who can give a more complete answer than I
can off the top of my head.  (Hint:  If p is a prime number and b
is any base, look at the values of (b mod p), (b^2 mod p), (b^3 mod p)
and so on.)

-- Raymond Chen <raymond@math.berkeley.edu>

4: Check last 2 digits.  For instance, anything ending in 24 is divisible
by 4, since 24 is divisible by 4.

6: No [ Editor: i.e., no rule like the one for 3 ].  Check for 2 and 3.

7: Chop off the last digit, then subtract twice its value.  Keep doing
until you're down to something small.

8: Last 3 digits.

-- Kenneth Arromdee <arromdee@crabcake.cs.jhu.edu>