Ruban de Pascal

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

Les rubans de Pascal correspondent à une technique servant à déterminer si un nombre entier N est divisible par un autre entier D en utilisant les chiffres de l'écriture de N dans une base B. Les fondements théoriques de cette méthode relèvent de la théorie de congruence. Pourtant il est intéressant de noter que Blaise Pascal a proposé sa méthode avant que cette théorie soit établie.

Pascal a décrit cette méthode dans De numeribus multiplicibus^[1].

[modifier] Construction d’un ruban

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 par D. Pour une base B=10 et D=7, on a :

$100 = 0 * 7 + 1$
$101 = 1 * 7 + 3$
$102 = 14 * 7 + 2$
$103 = ? * 7 + 6$
$104 = ? * 7 + 4$
$105 = ? * 7 + 5$
$106 = ? * 7 + 1$
$107 = ? * 7 + 3$
$108 = ? * 7 + 2$
$109 = ? * 7 + 6$

Ceci produit la suite 1,3,2,6,4,5,1,3,2,6… qui semble se répéter. La séquence 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.

[modifier] Premiers rubans en base 10

Les premiers rubans de Pascal en base 10 sont :

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

[modifier] Usage d’un ruban pour la divisibilité

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 a savoir si 123456789 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 123456789 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 123456789 à 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 chiffre et élément 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 + 3 = 8. 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.

[modifier] Correction du critère de divisibilité

L’explication du fonctionnement des rubans de Pascal se fait naturellement à travers les congruences. On dit que a congrue à b modulo c si le reste de la division entière de a par c est égal au reste de la division de b par c (ou encore que a-b est multiple de c). On le note $a \equiv b [c]$ . Par exemple :

$8 \equiv 13 \equiv 3 [5]$

Nous rappelons deux résultats importants concernant les congruences:

$a \equiv b [m], c \equiv d [m] \implies a*c \equiv b*d [m]$
$a \equiv b [m], c \equiv d [m] \implies a+c \equiv b+d [m]$

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

$B^i \equiv r_i [D]$ par construction
$c_i * B^i \equiv c_i * r_i [D]$ par produit de congruences
$N=\sum_i c_i * B^i \equiv \sum_i c_i * r_i [D]$ par somme de congruences

$c i$ est le chiffre dans l'écriture de N en base B, $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

∑	c_i * r_i
i

l'est aussi.

[modifier] Quelques propriétés des rubans

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, la fin du ruban est périodique constant.
Si 0 n'apparaît pas, l'un des restes différent de zéro se répète. Alors $B p$ congrue à $B m$ . Donc $B p + k$ congrue à $B m + k$ , ce qui prouve que le ruban est 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.