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 A = 1234567 while 102·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 di of division of ai by F. Alternately, replace di by (F - di) and write the result in the reverse order. The resulting number will be divisible by F depending whether A is itself divisible or not.

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 (F - di). One can begin with the first digit as well as the second. However, as we shall later see, if we also have to find the remainder of the division by F, it is quite advantageous to make sure that the first digit of the number written in reverse has not been modified. Thus given a sequence of remainders, replace them with their additive inverses starting from the second remainder on the right and move leftwards. This will guarantee that the rightmost remainder has not been changed.

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 A = 38391787 is divisible by 7.

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. To form a number, the left digit of the two digit "parts" must be carried over:

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:

  1. All three are mutually prime with 10.

  2. 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 A = 876345321. We proceed as indicated below:

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, 10·467 = 1 (mod 7). Since 10 = 3 (mod 7) and 3·5 = 1 (mod 7), 467 = 5 (mod 7).

Further, 102·74166 = 2 (mod 7). (Note that since n = 2 and even here, I replaced the remainder 5 with 2 = 7 - 5.) Since 100 = 2 (mod 7), 74166 = 1 (mod 7). And lastly, 104·876345321 = 6 (mod 7). (Again, use 6 = 7 - 1 and not 1, because n = 4 and is even.) Since 104 = 4 (mod 7) and 4·5 = 6 (mod 7), we conclude that

(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 106 = 103102101. 106 = 1 (mod 11). Therefore, 47119276 = 6 (mod 11).


Related material
Read more...

  • Divisibility Criteria
  • Fermat's Little Theorem
  • Divisibility Criteria (Further Examples)
  • Criteria of divisibility by 9 and 11
  • Division by 81
  • 5109094x171709440000 = 21!, find x
  • When 3AA1 is divisible by 11?
  • |Contact| |Front page| |Contents| |Algebra|

    Copyright © 1996-2018 Alexander Bogomolny

    71471137