Blaise Pascal (1623 – 1662) a inventé une méthode ingénieuse pour calculer le reste d’une division (sans l’effectuer) et donc de tester la divisibilité d’un nombre par un autre, que nous nommerons n dans la suite de cet article.
Une suite de restes
Pascal considère la suite des restes des puissances de 10 par n en commençant par 0, pour n = 7, cela donne :
| puissances | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| restes | 1 | 3 | 2 | 6 | 4 | 5 | 1 | 3 | 2 | 6 | 4 | 5 | 1 | 3 |
En effet, le reste de 1 est 1, celui de 10 est 3, celui de 100 est 2 (puisque 100 = 14 x 7 + 2), etc. La suite des restes est périodique. Ce résultat n’est pas lié au nombre 7, il est général. Cette suite est appelée le ruban de Pascal associé au nombre 7.
Calcul du reste d’une division
A partir de ce ruban, pour calculer le reste de la division par 7 d’un nombre comme 348, on écrit les décimales de 348 dans l’ordre inverse en dessous du début du ruban :
| ruban | 1 | 3 | 2 | |
| nombre | 8 | 4 | 3 | |
| calculs | 8 | 12=5 | 6 | 8+5+6=5 |
On effectue d’abord les multiplications en colonnes de 1 par 8, 3 par 4 et 2 par 3. On retranche autant de fois 7 que possible, donc 12 est remplacé par 5. On additionne alors les résultats obtenus et on retranche à nouveau autant de fois 7 que possible, on trouve 5 qui est le reste de la division de 348 par 7.
Pourquoi ? Cela vient des règles de calcul sur les nombres modulo 7 (c’est-à-dire en ne gardant à chaque étape que le reste dans la division par 7). On part de 348 = 3.102 + 4.101 + 8.100. En remplaçant, les puissances de 10 par leurs restes, on obtient 348 = 3.2 + 4.3 + 8.1 mod 7. On effectue les multiplications et les additions en retranchant 7 autant de fois qu’on peut et on a montré le bien fondé de l’algorithme utilisé ainsi que sa généralité.
On peut ainsi calculer très rapidement le reste des divisions de très grands nombres, comme celui de 56 218 491 par 7.
| ruban | 1 | 3 | 2 | 6 | 4 | 5 | 1 | 3 | |
| nombre | 1 | 9 | 4 | 8 | 1 | 2 | 6 | 5 | |
| calculs | 1 | 27=6 | 8=1 | 48=6 | 4 | 10=3 | 6 | 15=1 | 0 |
On trouve rapidement que le reste est égal à 0 donc que 56 218 491 est divisible par 7. Le test de divisibilité par 7 est donc de même nature que le test de divisibilité par 9 : au lieu de faire la somme des chiffres, on en fait une combinaison linéaire dont les coefficients sont ceux du ruban de Pascal. Il en est de même pour tous les nombres.
Divers rubans
Pour utiliser cette technique, il est bon de disposer d’un certain nombre de rubans. Voici ceux des nombres premiers inférieurs à 20 où on s’est arrêté à la partie périodique :
| Nb | |||||||||||||||||||
| 2 | 1 | 0 | |||||||||||||||||
| 3 | 1 | 1 | |||||||||||||||||
| 5 | 1 | 0 | |||||||||||||||||
| 7 | 1 | 3 | 2 | 6 | 4 | 5 | 1 | ||||||||||||
| 11 | 1 | 10 | 1 | ||||||||||||||||
| 13 | 1 | 10 | 9 | 12 | 3 | 4 | 1 | ||||||||||||
| 17 | 1 | 10 | 15 | 14 | 4 | 6 | 9 | 5 | 16 | 7 | 2 | 3 | 13 | 11 | 8 | 12 | 1 | ||
| 19 | 1 | 10 | 5 | 12 | 6 | 3 | 11 | 15 | 17 | 18 | 9 | 14 | 7 | 13 | 16 | 8 | 4 | 2 | 1 |
On peut ainsi facilement déterminer le reste d’un nombre comme 521 365 941 dans la division par 19.
| 1 | 10 | 5 | 12 | 6 | 3 | 11 | 15 | 17 | |
| 1 | 4 | 9 | 5 | 6 | 3 | 1 | 2 | 5 | |
| 1 | 40=2 | 45=7 | 60=3 | 36=17 | 9 | 11 | 30=11 | 85=9 | 1+2+7+3+17+9+11+11+9=13 |
Le reste de 521 365 941 dans la division par 19 est donc 13.