La charge de la preuve

Je fais partie d'une génération qui faisait ses calculs à la main et qui, l'erreur étant si humaine, utilisait l'un des systèmes de détection d'erreur les plus extraordinaires, la preuve par 9. J'ai appris à utiliser la preuve par 9 à l'école primaire, mais je n'ai compris le pourquoi de son efficacité que bien plus tard au lycée, ce qui m'a permis d'envisager d'autres tests d'erreurs similaires comme la preuve par 2 ou la preuve par 10. Le but de ce billet est de montrer les dessous de ces tests et d'essayer de comparer mathématiquement leur efficacité.

Pour comprendre la preuve par 9, commençons par écrire tous les nombres entiers naturels dans un tableau à 9 colonnes, comme ci-dessous. 

Une propriété remarquable de ce tableau peut être présentée ainsi :

• choisissez deux colonnes
• choisissez deux nombres, un par colonne
• le produit des deux nombres choisis se trouvera toujours dans la même colonne.

Par exemple, choisissons le nombre 11 dans la colonne de 2 et le nombre 12 dans la colonne de 3. Le produit de 11 par 12 est 132 et il se trouve dans la colonne de 6. Mais si l'on avait choisi 38 dans la colonne de 2 et 3 dans la colonne de 3, leur produit 114 se trouverait encore dans la colonne de 6. On peut résumer cela en disant que le produit d'un nombre de la colonne de 2 par un nombre de la colonne de 3 se trouve obligatoirement dans la colonne de 6. Cela définit une arithmétique des colonnes pour laquelle  col(2) * col(3) = col(6), mais aussi col(4) * col(5) = col(2), ou col(3) * col(6) = col(0). Il s'agit de l'arithmétique modulo 9 (9 car on est parti de 9 colonnes).

Considérons maintenant le produit 129 * 137. 129 se trouve dans la colonne de 3 et 137 se trouve dans la colonne de 2. On sait que le produit 129 * 137 doit se trouver dans la colonne de 6. Supposons qu'après avoir effectué l'opération on trouve 17673. La preuve par 9 nous dit que si 17673 n'est pas dans la colonne de 6, alors 17673 n'est pas le produit de 129 par 137 et une erreur de calcul s'est produite. Par contre si 17673 est dans la colonne de 6, aucune conclusion n'est possible car il y a bien d'autres nombres dans la colonne de 6. Dans 8 cas sur 9 la preuve par 9 détecte une erreur et dans 1 cas sur 9 elle ne permet pas de conclure.

Il reste un petit détail à régler : comment trouver dans quelle colonne se trouve un nombre sans être obligé d'écrire le tableau jusqu'à ce nombre ? On comprend très vite que le premier terme de la colonne d'un nombre n est simplement le reste de la division de n par 9. Trouver la colonne de 17673 revient donc à trouver le reste de la division de 17673 par 9. Par chance ce reste est facile à trouver car tout entier n a le même reste dans sa division par 9 que la somme de ses chiffres. Ainsi le reste de la division de 17673 par 9 est aussi le reste de la division de 1+7+6+7+3=24 par 9, et donc aussi le reste de la division de 2+4=6 par 9, et donc tout simplement 6. Nous avons donc trouver que 17673 est dans la colonne de 6.

On peut imaginer d'autres "preuves" en changeant le nombre de colonnes choisi au départ.

Remplaçons 9 par 2. On aura une colonne pour les nombres pairs (colonne de 0) et une colonne pour les nombres impairs (colonne de 1). La preuve par 2 consistera à faire une vérification sur la parité du résultat. Cette vérification détecte une erreur dans 1 cas sur 2 et ne permet pas de conclure dans 1 cas sur 2. Elle est simple à mettre en oeuvre mais a un faible rendement.

Remplaçons 9 par 10. On aura 10 colonnes très simples à caractériser : la colonne de 0 contient les nombres qui se terminent par 0, la colonne de 1 contient les nombres qui se terminent par 1, la colonne de 2 contient les nombres qui se terminent par 2, etc ... Le reste de la division d'un nombre par 10 est simplement le dernier chiffre de ce nombre. La preuve par 10 consiste donc à faire le test du dernier chiffre. Elle détecte une erreur 9 fois sur 10 et ne permet pas de conclure 1 fois sur 10.

Cela m'amène à mettre en évidence la bizarrerie suivante : la preuve par 9 ne permet pas de conclure 1 fois sur 9 alors que la preuve par 10 ne permet pas de conclure 1 fois sur 10, donc moins souvent. Autrement dit, la preuve par 10 détecte plus souvent les erreurs que la preuve par 9.

Pourtant on enseignait la preuve par 9 et pas la preuve par 10...

PS: ce n'est pas parce qu'il utilise la preuve par neuf qu'un mathématicien est pour l'innovation.