Ruban de Pascal

Dans le reste de l'article, N désigne le nombre dont on souhaite connaître la divisibilité par le nombre noté D et B désigne la base dans laquelle le nombre N est écrit.

Le principe des rubans est d'identifier, pour chaque puissance de la base B, le reste dans sa division euclidienne par D. Pour une base B = 10 et D = 7, on a :

• ${\displaystyle 10^{0}=0*7+1}$
• ${\displaystyle 10^{1}=1*7+3}$
• ${\displaystyle 10^{2}=14*7+2}$
• ${\displaystyle 10^{3}=?*7+6}$
• ${\displaystyle 10^{4}=?*7+4}$
• ${\displaystyle 10^{5}=?*7+5}$
• ${\displaystyle 10^{6}=?*7+1}$
• ${\displaystyle 10^{7}=?*7+3}$
• ${\displaystyle 10^{8}=?*7+2}$
• ${\displaystyle 10^{9}=?*7+6}$

Ceci produit la suite 1,3,2,6,4,5,1,3,2,6… qui semble se répéter. La suite des restes constitue le ruban de Pascal en base B pour le diviseur D. C'est ce ruban que l'on utilisera pour savoir si N est divisible par D.

Les premiers rubans de Pascal en base 10 sont :

1. 0…
2. 1, 0…
3. 1, 1…
4. 1, 2, 0…
5. 1, 0…
6. 1, 4, 4…
7. 1, 3, 2, 6, 4, 5, 1, 3, 2, 6…
8. 1, 2, 4, 0…
9. 1, 1…

L’utilisation d'un ruban de Pascal pour tester la divisibilité passe par la transformation du nombre fourni en un autre plus petit ayant le même reste dans la division par D.

En commençant par un exemple, on cherche à savoir si 123 456 789 est divisible par 3.

Le ruban de Pascal de 3 est 1, 1, 1, 1, 1… Le nouveau nombre est donc 1 × 1 + 1 × 2 + 1 × 3 + 1 × 4 + 1 × 5 + 1 × 6 + 1 × 7 + 1 × 8 + 1 × 9 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45.

Est-ce que 123 456 789 est divisible par 7 ? Il faut commencer par aligner le nombre avec le ruban de 7 en commençant par la droite, pour cela on écrit 123 456 789 à l'envers :

• 9 8 7 6 5 4 3 2 1
• 1 3 2 6 4 5 1 3 2

Ensuite, on fait la somme des produits entre chiffres et éléments du ruban : 9 × 1 + 8 × 3 + 7 × 2 + 6 × 6 + 5 × 4 + 4 × 5 + 3 × 1 + 2 × 3 + 1 × 2 = 134. Si on le souhaite, on peut alors recommencer :

• 4 3 1
• 1 3 2

Ce qui nous donne 4 × 1 + 3 × 3 + 1 × 2 = 15. Essayons encore une fois :

• 5 1
• 1 3

5 + 3 = 8 n'est pas multiple de 7, 123456789 non plus, tout comme 134 ou 15. Par ailleurs, tous ces nombres ont le même reste dans une division par 7 : ce reste est 1.

Par commodité, on peut aussi écrire le ruban de droite à gauche, et dans ce cas garder l'ordre naturel des chiffres dans l'écriture de N.

L’explication du fonctionnement des rubans de Pascal se fait naturellement à travers les congruences. On dit que a congru à b modulo c si, pour la division euclidienne par c, a et b ont même reste (ou encore si a – b est multiple de c). On le note ${\displaystyle a\equiv b\mod c}$. Par exemple :

${\displaystyle 8\equiv 13\equiv 3\mod 5}$

Deux résultats sont importants concernant les congruences :

• ${\displaystyle a\equiv b\mod m,c\equiv d\mod m\Rightarrow a\times c\equiv b\times d\mod m.}$
• ${\displaystyle a\equiv b\mod m,c\equiv d\mod m\Rightarrow a+c\equiv b+d\mod m.}$

Le but est ici de montrer que la somme des produits (élément du ruban × chiffre) est congrue au nombre lui-même :

• ${\displaystyle B^{i}\equiv r_{i}\mod D}$ par construction,
• ${\displaystyle c_{i}\times B^{i}\equiv c_{i}\times r_{i}\mod D}$ par produit de congruences,
• ${\displaystyle N=\sum _{i}c_{i}\times B^{i}\equiv \sum _{i}c_{i}\times r_{i}\mod D}$ par somme de congruences.

${\displaystyle c_{i}}$ est le chiffre dans l'écriture de N en base B, ${\displaystyle r_{i}}$ est l'élément du ruban de D en base B. La conséquence directe de la dernière ligne est que si N est un multiple de D alors ${\displaystyle \sum _{i}c_{i}\times r_{i}}$ l'est aussi.

• Le nombre de restes possibles dans la division par D est fini et égal à D (de 0 à D – 1) ; il y a donc obligatoirement répétition.
• Si 0 apparaît dans le ruban, tous les éléments suivants sont des zéros car si B^p est un multiple de D, toutes les puissances suivantes, qui sont des multiples de B^p, sont aussi des multiples de D. Dans ce cas, à partir du rang p, le ruban est constant, c'est-à-dire périodique et de période 1.
• Si 0 n'apparaît pas, l'un des restes différent de zéro se répète. Alors B^p est congru à B^m donc B^p+k est congru à B^m+k, ce qui prouve que le ruban est, à partir du rang p, périodique et de période m – p. Le nombre de restes possibles, 0 exclu, étant D – 1, la période est inférieure ou égale à D – 1.
• On obtient un ruban dont le fonctionnement (qui détermine la classe de congruence modulo c d'un nombre) est tout aussi correct lorsqu'on remplace chaque nombre du ruban par n'importe quel nombre qui lui est congru modulo c. Par exemple pour c = 7, un ruban équivalent à 1, 3, 2, 6, 4, 5… est 1, 3, 2, –1, –3, –2…

Jacques Sakarovitch, « La machine à diviser de Monsieur Pascal » — Une discussion sur les rubans et leur transformation en automates.