Home

> urticator.net
  Search

  About This Site
> Domains
  Glue
  Stories

  Computers
  Driving
  Games
  Humor
  Law
  Math
> Numbers
  Science

  Powers and Fractions
  Notes About Squares
  Decimal Expansions
  Repeat Length Again
  Number Maze
  Primes
> Divisibility
  Intrinsic Nature of Primes
  Other Topics
  Other Topics (2)

  Reduction Rules
  Other Methods
  In Other Bases

Divisibility

Here I want to talk about divisibility tests and various related things.

I first became interested in divisibility when I learned that I could test divisibility by 3 or 9 by first adding up all the digits in a number and then testing whether the result was divisible. That seemed like the strangest thing! Naturally I wanted to understand why it worked.

The way I see it now, it's a fact about congruence mod 9. For example,

538 = 5×(99+1) + 3×(9+1) + 8 ≡ 5 + 3 + 8 = 16 mod 9.

Then, since 538 and 16 differ by a multiple of 9, one is divisible by 3 or 9 if and only if the other is.

Once you understand that, you can do the same thing for other divisors. For example,

538 = 5×(98+2) + 38 ≡ 5×2 + 38 = 48 mod 7.

In other words, you can test divisibility by 7 by first grouping the digits in pairs and then doubling each pair and adding it to the next one. Here's how the method works for a larger number, 123456. The part in bold is roughly what your train of thought should be.

123456
243456
5856
11656
172

More generally, if you want to test divisibility by m, what you need to do is choose small numbers k and d such that the following equation holds.

10k ≡ d mod m

Then you can test divisibility by m by grouping the digits in sets of size k and multiplying each set by d before adding it to the next one.

Sometimes there's more than one plausible choice. For example, here's what I consider to be all the possibilities for m = 7.

kd
13
22
3-1
61

Now, there's another way to look at the equation above. Instead of fixing m and searching for small numbers k and d, we can do the reverse: enumerate all the useful values of k and d and see for which values of m each one works. And, that's easy. The equation means that 10k-d is divisible by m, so all we have to do is find the factors of 10k-d.

The only question, then, is what counts as useful. If we require that the number of digits be at most three, and that the multiplier be at most two, here's what we get.

8 =2398 =2 72998 =2 499
9 =3299 =32 11999 =33 37
11 =prime101 =prime1001 =7 11 13
12 =22 3102 =2 3 171002 =2 3 167

So, for example, because 13 is a factor of 1001, we can test divisibility by 13 by adding digits in sets of three with alternating signs, like so.

123456 = 123×(1001-1) + 456 ≡ -123 + 456 = 333 mod 13

You might recognize many of the numbers above from what I said about fractions (in base N) and other denominators. That's not a coincidence—the fact that a number m divides 10k-d provides both a way to test divisibility by m and a way to expand the fraction 1/m in a power series. The k = 2 test for divisibility by 7, for example, derives from the same source as the interesting expansion of 1/49. Still, although it's not a coincidence, it does surprise me that the two are related.

There are two more points I need to make, then I'll be able to summarize everything in a table.

First, you can test divisibility by a composite number by splitting the divisor into relatively prime parts. A number is divisible by 21, for example, if and only if it's divisible by 3 and 7. A power of a prime number, however, can't be split, so you need a specific test for each power. If, say, you want to test divisibility by 27, knowing the test for 9 doesn't help, instead you need to know that 27 goes into 999.

Second, the tests for powers of 2 and 5 are special cases. To test divisibility by 4, for example, you only need to look at the last two digits of the number, because 100 is evenly divisible by 4. (In other words, d = 0.)

123456 = 1234×(100+0) + 56 ≡ 56 mod 4

Now, as I said, I can summarize everything. Here are all the useful divisibility tests for small m. The symbol {k,d} represents the test with set size k and multiplier d.

2last digit
3{1,1}
4last two digits
5last digit
6check 2 and 3
7{2,2} or {3,-1}
8last three digits
9{1,1}
10last digit
11{1,-1} or {2,1}
12check 3 and 4
13{3,-1}
14check 2 and 7
15check 3 and 5
16last four digits
17{2,-2}
18check 2 and 9

That's a convenient place to stop, since there's no good test for divisibility by 19. (Actually, you can construct one using the fact that 2×10 ≡ 1 mod 19, but it's not the same kind of test as the others.)

That's all I wanted to say about divisibility tests. Now, on to related things!

next

 

  See Also

  Associative Hooks
  Four Digits
  In Other Bases
  Other Methods
  Primes
  Repunits

@ July (2004)