# Divisibility by 7, 11, and 13

Gustavo Toja from Brasil came up with an interesting method of divisibility by 7. As we shall see, the method also works to verify the divisibility by 11 and 13.

Accordingly, let F be one of these numbers, 7, 11, or 13.

Any given number A written in the decimal system admits a representation into two digit numbers:

A = Σ 10^{2i} a_{i},

where Σ is a shorthand symbol for "sum" and index i ranges from 0 to the greatest value n such that 10^{2n} does not exceed A. For example,

1234567 = 10^{6}·1 + 10^{4}·23 + 10^{2}·45 + 67.

(Here i = 0, 1, 2, 3 and n = 3 because 10^{2·4} is already greater than ^{2·3} is still less than A.) As we see, the leftmost member of the representation may be a one-digit number.

The procedure is as follows: Find the remainders d_{i} of division of a_{i} by F. Alternately, replace d_{i} by _{i})

### Remark

If the divisibility of A is all we need to determine, it does not matter where you start replacing d_{i} with its additive inverse _{i})

If you prefer to think in terms of "moving rightwards", then the rule is this: Let n be the number of the 2-digit parts of A. For n even, replace d_{i} starting with d_{n-1}, the leftmost remainder; for n odd, start with d_{n-2}, the second remainder.

To use Gustavo's original example: check that

First split A into two digit numbers:

38 39 17 87

Next find the remainders of division of these numbers by 7:

3 4 3 3

Replace every other remainder with its additive inverse modulo 7:

4 3 4 4

Consider the number having the above digits but written in the reverse order: 3444. Apply the same procedure to 3444:

43 44 => 1 2 => 21.

Since 21 is divisible by 7, so is 3444 and also 38391787!

Let's take another example: F = 11 and A = 4711927.

4 71 19 27 => 4 5 8 5 = > 7 5 3 5 =>

5357 => 53 57 => 9 2 => 2 2 => 22.

Conclude: since 22 is divisible by 11, so is 5357, and so is 4711927. And one more example: F = 13, A = 61255051.

61 25 50 51 => 9 12 11 12 => 4 12 2 12.

In this case, the remainders written in the reverse order give the sequence:

12 2 12 4 => 12324 => 1 23 24 =>

1 10 11 => 1 3 11 => 11 3 1 =>

1131 => 11 31 => 11 5 => 2 5 = 52.

Conclude: since 52 is divisible by 13, so is 12324 and, consequently, 61255051.

Now, what is the explanation for this property of the three numbers: 7, 11, 13. What do they have in common? (They are of course consecutive primes, but this is not important for the problem at hand.) Two things are important:

All three are mutually prime with 10.

7×11×13 = 1001.

The first property implies that, for any A and any power 10^{n} of 10,

F divides A iff F divides F·10^{n}, or, in short,

F|A iff F|10^{n}A.

The second property implies

1000 = -1 (mod F),

So that 10^{3k} = (-1)^{k (mod 2)}. It then follows that

10^{n + 2k} = (-1)^{k (mod 2)}10^{n - k} (mod F).

Let M = Σ 10^{i} m_{i} = 10^{2n}m_{n} + 10^{n-1}m_{n-1} + 10^{2n-4}m_{n-2} + ... + 10^{2}m_{1} + m_{0}. Then modulo F

(1)

10^{n}·M = 10^{n}m_{0} - 10^{n-1}m_{1} + 10^{n-2}m_{2} + ... + (-1)^{n}·m_{n} (mod F),

where the sign depends on the parity of n. The above actually completes the proof of the claimed property.

This appears to be an additional example of a more general theory.

Going backwards we can naturally determine also the remainder of division by any of the three numbers 7, 11, 13. One note of caution: depending on the parity of n, two cases should be considered. Assume d_{i} is the remainder of division of m_{i} by F or its additive inverse. Then

(2)

10^{n}·M = d_{0}d_{1} ... d_{n} (mod F).

Moving backwards, we shall use our knowledge of the remainder of d_{0}d_{1} ... d_{n} to determine that of M. The two are the same if d_{n} is the remainder of m_{0} as opposed to being its inverse. This explains the above rule of the thumb.

Let's now consider an example: let F = 7 and

876345321 => 8 76 34 53 21 => 1 6 6 4 0 => 6 6 1 4 7=>

74166 => 7 41 66 => 0 6 3 => 7 6 4 =>

467 => 4 67 => 4 4 => 34 => 43.

The remainder of division of 43 by 7 is 1. Therefore,

Further, 10^{2}·74166 = 2 (mod 7). (Note that since ^{4}·876345321 = 6 (mod 7).^{4} = 4 (mod 7)

(3)

876345321 = 5 (mod 7).

The process can be simplified. In all we had to employ (1) three times, multiplying successively by 10, 10^{2} and 10^{4}. The total power of 10 used in (1) was 5. Two of the powers (2 and 4) were even and incurred the use of the additive inverse. Since the number of reversals was even, they cancelled each other, which implies that

10^{5}·876345321 = 1 (mod 7).

But 10^{7} = 3 (mod 7) and 3·5 = 1 (mod 7), so again we obtain (3).

And for a final example, let F = 11 and A = 47119276. We proceed as follows:

47119276 => 47 11 92 76 => 3 0 4 10 => 8 0 7 10 =>

10708 => 1 07 08 => 1 7 8 => 1 4 8 =>

841 => 8 41 => 8 8 => 3 8 => 83.

83 = 6 (mod 11). The total power of 10 that has been implicitly used in the example is ^{6} = 10^{3}10^{2}10^{1}.^{6} = 1 (mod 11).

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

64641141 |