Test for divisibility by 13

Posted on by John

There are simple rules for telling whether a number is divisible by 2, 3, 4, 5, and 6.

  • A number is divisible by 2 if its last digit is divisible by 2.
  • A number is divisible by 3 if the sum of its digits is divisible by 3.
  • A number is divisible by 4 if the number formed by its last two digits is divisible by 4.
  • A number is divisible by 5 if its last digit is divisible by 5.
  • A number is divisible by 6 if it is divisible by 2 and by 3.

There is a rule for divisibility by 7, but it’s a little wonky. Let’s keep going.

  • A number is divisible by 8 if the number formed by its last three digits is divisible by 8.
  • A number is divisible by 9 if the sum of its digits is divisible by 9.
  • A number is divisible by 10 if its last digit is 0.

There’s a rule for divisibility by 11. It’s a little complicated, though not as complicated as the rule for 7. I describe the rule for 11 in the penultimate paragraph here.

A number is divisible by 12 if it’s divisible by 3 and 4. (It matters here that 3 and 4 are relatively prime. It’s not true, for example, that a number is divisible by 12 if it’s divisible by 2 and 6.)

But what do you do when you get to 13?

Testing divisibility by 7, 11, and 13

We’re going to kill three birds with one stone by presenting a rule for testing divisibility by 13 that also gives new rules for testing divisibility by 7 and 11. So if you’re trying to factor a number by hand, this will give a way to test three primes at once.

To test divisibility by 7, 11, and 13, write your number with digits grouped into threes as usual. For example,

11,037,989

Then think of each group as a separate number — e.g. 11, 37, and 989 — and take the alternating sum, starting with a + sign on the last term.

989 – 37 + 11

The original number is divisible by 7 (or 11 or 13) if this alternating sum is divisible by 7 (or 11 or 13 respectively).

The alternating sum in our example is 963, which is clearly 9*107, and not divisible by 7, 11, or 13. Therefore 11,037,989 is not divisible by 7, 11, or 13.

Here’s another example. Let’s start with

4,894,498,518

The alternating sum is

518 − 498 + 894 – 4 = 910

The sum takes a bit of work, but less work than dividing a 10-digit number by 7, 11, and 13.

The sum 910 factors into 7*13*10, and so it is divisible by 7 and by 13, but not by 11. That tells us 4,894,498,518 is divisible by 7 and 13 but not by 11.

Why this works

The heart of the method is that 7*11*13 = 1001. If I subtract a multiple of 1001 from a number, I don’t change its divisibility by 7, 11, or 13. More than that, I don’t change its remainder by 7, 11, or 13.

The steps in the method amount to adding or subtracting multiples of 1001 and dividing by 1000. The former doesn’t change the remainder by 7, 11, or 13, but the latter multiplies the remainder by −1, hence the alternating sum. (1000 is congruent to -1 mod 7, mod 11, and mod 13.) See more formal argument in footnote [1].

So not only can we test for divisibility by 7, 11, and 13 with this method, we can also find the remainders by 7, 11, and 13. The original number and the alternating sum are congruent mod 1001, so they are congruent mod 7, mod 11, and mod 13.

In our first example, n = 11,037,989 and the alternating sum was m = 963. The remainder when m is divided by 7 is 4, so the remainder when n is divided by 7 is also 4. That is, m is congruent to 4 mod 7, and so n is congruent to 4 mod 7. Similarly, m is congruent to 6 mod 11, and so n is congruent to 6 mod 11. And finally m is congruent to 1 mod 13, so n is congruent to 1 mod 13.

Related posts

[1] The key calculation is
10^3 \equiv -1 \bmod 1001 \implies \sum_{i=0}^n a_i10^{3i} \equiv \sum_{i=0}^n (-1)^ia_i \bmod 1001

6 thoughts on “Test for divisibility by 13”

  1. Ken Abbott

    Nice. But can you generalize this to test divisibility by any prime? (I think you can see what I’m getting at.)

  2. John

    It generalizes to any prime that divides 10^k + 1. But when k is as big as the number of digits in the number you want to factor, the method doesn’t buy you anything.

    For example, 10001 = 73*137. So you could group digits in quartets and apply the analogous rule to test divisibility by 73 and 137. It would be convenient if you could test divisibility by smaller primes this way, like 17 or 19, but that’s not the case.

    Now 10^8 + 1 is divisible by 17, so you could group digits into octets and do the analogous rule, but that’s no help if your number has eight digits or less.

  3. Kaleberg

    There was an old elementary school math exercise where the teacher would ask the students to each choose a three digit number then multiply it by 7, 11 and 13 in any particular order. The surprise was that one got a six digit number consisting of one’s original three digits repeated. The kids who couldn’t multiply didn’t get it. The really bright kids multiplied 7 times 11 times 13 and sat around smugly.

  4. Nathan Hannon

    If a prime divides 10^k-1, you can do the same thing without the alternating signs. In fact, most good divisibility rules boil down to something being a factor of either 10^k-1, 10^k, or 10^k+1 (with appropriate generalizations to divisibility rules in other bases).

  5. xpil

    Great article, as always!

    One little typo though. Instead of:
    “Similarly, m is congruent to 6 mod 11, and so m is congruent to 6 mod 11.”
    this should read:
    “Similarly, m is congruent to 6 mod 11, and so n is congruent to 6 mod 11.”

    Have a good one.

Comments are closed.