Ouvrir le menu principal

Ruban de Pascal

algorithme mathématique

Le terme ruban de Pascal renvoie à une technique servant en particulier à 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 sur les entiers. Le ruban permet, plus précisément, de calculer la classe de congruence de N modulo D.

Blaise Pascal a proposé sa méthode dans De numeribus multiplicibus[1] avant que cette théorie ne soit établie.

Sommaire

Construction d’un rubanModifier

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 :

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

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.

Premiers rubans en base 10Modifier

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…

Usage d’un ruban pour la divisibilitéModifier

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.

Correction du critère de divisibilitéModifier

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  . Par exemple :

 

Deux résultats sont importants concernant les congruences :

  •  
  •  

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

  •   par construction,
  •   par produit de congruences,
  •   par somme de congruences.

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

Quelques propriétés des rubansModifier

  • 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 Bp est un multiple de D, toutes les puissances suivantes, qui sont des multiples de Bp, 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 Bp est congru à Bm donc Bp+k est congru à Bm+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…

Notes et référencesModifier

  1. Blaise Pascal, Œuvres de Blaise Pascal, Volume 5, (la) De Numeribus Multiplicibus, p. 117.

Lien externeModifier

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