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}\equiv 1\mod 7}$
• ${\displaystyle 10^{1}\equiv 3\mod 7}$
• ${\displaystyle 10^{2}\equiv 2\mod 7}$
• ${\displaystyle 10^{3}\equiv 6\mod 7}$
• ${\displaystyle 10^{4}\equiv 4\mod 7}$
• ${\displaystyle 10^{5}\equiv 5\mod 7}$
• ${\displaystyle 10^{6}\equiv 1\mod 7}$
• ${\displaystyle 10^{7}\equiv 3\mod 7}$
• ${\displaystyle 10^{8}\equiv 2\mod 7}$
• ${\displaystyle 10^{9}\equiv 6\mod 7}$

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 :

	100	101	102	103	104	105
1	0	0	0	0	0	0
2	1	0	0	0	0	0
3	1	1	1	1	1	1
4	1	2	0	0	0	0
5	1	0	0	0	0	0
6	1	4	4	4	4	4
7	1	3	2	6	4	5
8	1	2	4	0	0	0
9	1	1	1	1	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	5	4	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.

Summarize Timeline Fact Check

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.