Méthode de Sylvio Moura Velho (2005) pour la divisibilité par 7 ou par 13

« To start the first step you need to take the value of the rightmost digit of the given number, skip the next digit and subtract from that value the sum of the following pair of digits. After this, always proceeding from right to left, you need to skip the next digit and add the  remainder to the sum of the following pair of digits. Repeat this procedure all the way through the number, skiping one digit and taking the sum of the following pair of digits, alternating subtractions and additions. When you have no more pairs to subtract or to add, if the result is a two-digits number, subtract from it a convenient multiple of seven (7, 14 or 21) to reduce it to just one digit. If in the process you have a minuned smaller than the subtrahend you need to add to the minuend a convenient multiple of 7. Sometimes, due to a particular extension of the given number, you will finish the first step adding or subtracting the value of a digit that has not a pair. Once you have finished the first step write down under the original number, in the place of the ones, the resulting digit.

                        The second step is pretty much the same as the first step. The only difference is that you need to start with the sum of the pair of digits next to the rightmost digit of the given number. The sequence of subtractions and additions, always from right to left, is in the same order.

                        When you finish the second step and write down the resulting digit in the place of the tens you have formed the reduced number: if the number formed by the two digits is a multiple of  7 then the original number is also a multiple of 7; if not, the division of both numbers by 7 will leave the same remainder. »

Explications: (pourquoi ça marche ) voir http://ken.duisenberg.com/potw/archive/arch05/050902.html

Explication de Jayavel Sounderpandian. (Septembre 2005)

The modulo 7 values of the sequence 1, 10, 100, Š is:

1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, Š where the six numbers repeat themselves.

The first digit that the method computes assigns the following six repeating values to the successive decimal places:

1, 0, -1, -1, 0, 1

Because 10 mod 7 = 3, the second digit that the method computes assigns the following six repeating values to the successive decimal places:

0, 3, 3, 0, -3, -3

Adding the two we get

1, 3, 2, -1, -3, -2

which in modulo 7 is the same as

1, 3, 2, 6, 4, 5.

Hence the method must work.

Surprisingly, testing divisibility by 13 reduces to analyzing 6 repeating residuals similarly, and the method works. This happens because of the combination of the facts:

10 mod 7 = 3

10 mod 13 = -3

10^6 mod 13 = 1

13 mod 7 = -1