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 = Σ 102i ai,
where Σ is a shorthand symbol for "sum" and index i ranges from 0 to the greatest value n such that 102n does not exceed A. For example,
1234567 = 106·1 + 104·23 + 102·45 + 67.
(Here i = 0, 1, 2, 3 and n = 3 because 102·4 is already greater than
The procedure is as follows: Find the remainders di of division of ai by F. Alternately, replace di by
Remark
If the divisibility of A is all we need to determine, it does not matter where you start replacing di with its additive inverse
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 di starting with dn-1, the leftmost remainder; for n odd, start with dn-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 10n of 10,
F divides A iff F divides F·10n, or, in short,
F|A iff F|10nA.
The second property implies
1000 = -1 (mod F),
So that 103k = (-1)k (mod 2). It then follows that
10n + 2k = (-1)k (mod 2)10n - k (mod F).
Let M = Σ 10i mi = 102nmn + 10n-1mn-1 + 102n-4mn-2 + ... + 102m1 + m0. Then modulo F
(1)
10n·M = 10nm0 - 10n-1m1 + 10n-2m2 + ... + (-1)n·mn (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 di is the remainder of division of mi by F or its additive inverse. Then
(2)
10n·M = d0d1 ... dn (mod F).
Moving backwards, we shall use our knowledge of the remainder of d0d1 ... dn to determine that of M. The two are the same if dn is the remainder of m0 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, 102·74166 = 2 (mod 7). (Note that since
(3)
876345321 = 5 (mod 7).
The process can be simplified. In all we had to employ (1) three times, multiplying successively by 10, 102 and 104. 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
105·876345321 = 1 (mod 7).
But 107 = 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


|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
72264159