Le Théorème de Rémi

Ce mercredi, nous étions sur les berges de l’île de la Barthelasse, sous le regard hautain du palais des Papes, mais le pont Saint-Bénezet, intéressé par les rythmes à venir, approchait déjà son pied à la gigue réputée. C’est alors que Rémi, architecte de son état mais sensible aux charmes mathématiques, me fit part d’un théorème – son théorème – découvert l’année de ses douze ans :

Si je multiplie 123456789 par 8, le résultat est 987654312

Voilà qui est surprenant, et on ne peut qu’apprécier l’élégance du phénomène, à peine gâchée par la malheureuse propension du 1 à imposer sa prééminence naturelle sur le 2, même dans cette situation. Vérifiez vous-même le calcul (vous devez bien disposer sur votre ordinateur d’une calculette quelconque?): il est tout à fait exact.

Pour ma part, je n’ai vérifié le calcul que le lendemain, à la main (c’est quand même plus savoureux!), et, comme j’imagine bon nombre de mes collègues, me suis demandé: cela est-il propre à l’écriture décimale, ou serait-ce valable dans toute base?

Certains d’entre vous se demandent sans doute quelle est cette histoire de « base » dont il est question ici? Pour ceux-là, je me dois d’apporter quelques éclaircissements. Voyez-vous, l’écriture des nombres qui vous est habituelle n’est qu’une parmi bien d’autres. Son statut privilégié est lié à notre habitude ancestrale de tout compter sur nos doigts, qui, pour les moins malchanceux d’entre-nous, sont bien au nombre de \(10\).

Le principe de l’écriture décimale consiste à regrouper toute collection en cours de comptage en paquets de \(10\), puis ces paquets de \(10\) (appelons les « dizaines ») en paquets de \(10\) paquets (les centaines, qui contiennent donc
chacun \(100=10\times10\) éléments), puis en paquets de \(10\) paquets de centaines, etc…
Le nombre d’ éléments qu’on n’a pas pu mettre dans une dizaine est le chiffre des unités, celui des dizaines qui ne sont pas dans un paquet de \(100\) (\(10\) paquets de dizaines) est le chiffre des dizaines (justement!), le nombre de paquets de \(100\) non-regroupés dans un paquet de \(1000\) est celui des centaines, etc…

Mais il y a bien sûr d’autres possibilités. Nous sommes par exemple déjà habitués à l’écriture sexagécimale héritée des suméro-babyloniens, avec laquelle nous persistons par exemple de mesurer le temps, bien qu’elle nous pose quotidiennement quelques petits casse-têtes familiers dûs à son mélange avec l’écriture décimale. Mais au moins songeons aux grands progrès apportés par les chiffres arabes par rapport à l’épouvantable écriture en chiffres romains!

Des chiffres et des pattes

Maintenant, voyons comment nos amis arachnoïdes ¹Nous ne nous intéresserons pas aux lombrics, à l’habilité arithmétique notoirement déplorable, et pour cause!, à la fin de chaque journée, comptent sur leurs \(8\) pattes le nombre de fois qu’elles ont réparé leur toile. Le nombre qui en base décimale s’écrit \(27\), elles le noteront \(33\). En effet, tout ensemble à \(27\) éléments se décompose en \(3\) paquets de \(8\), et avec un résidu de \(3\). En d’autres termes:

\[27 = 3 \times 8 + 3\]

De même, notre remarquable araignée va écrire le nombre \(121\) sous la forme \(171\), puisque:
\[121 = 1 \times 64 +57 = 1 \times 8^2 + 7 \times 8 +1\]

Elle aussi a écouté Rémi, et s’est donc demandé: diable, sachant que \(8\), le chiffre par lequel Rémi a multiplié \(123456789\), n’est autre que \(10-2\), que vais-je obtenir si je multiplie le nombre \(1234567\) formé des \(7\) chiffres de mon système, par \(8-2\), c’est-à-dire \(6\)? Et bien, dans son système « octal », elle obtient:
\[1234567 \times 6 = 7654312\]
Le chiffre \(1\) s’obstinant à ne pas se laisser dépasser par le pauvre \(2\).

Et oui. Il faut signaler que notre araignée a pris l’habitude de fréquenter les classes de l’école à côté (c’est sans doute pour çà qu’on n’y entend pas une mouche voler) et a appris les règles de la multiplication, qu’elle a su adapter à sa base \(8\). Je pose:

\[\begin{array}{ccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7\\
\times & & & & & & 6
\end{array}\]

Je multiplie le chiffre des unités \(7\) par \(6\), et j’obtiens \(42 = 5 \times 8 + 2\), c’est-à-dire \(52\) en base \(8\). J’écris donc \(2\) comme nouvelle unité, et j’ai la retenue \(5\).

\[\begin{array}{ccccccc}
1 & 2 & 3 & 4 & 5 & 6^5 & 7\\
\times & & & & & & 6 \\
& & & & & & 2
\end{array}\]

Pour le chiffre des « octaines », je multiplie \(6\) par \(6\), et ajoute la retenue \(5\). J’obtiens \(41=5\times 8 + 1\), ce qui s’écrit donc \(51\) en base \(8\). Le chiffre des octaines est donc \(1\), et la retenue à reporter est encore \(5\). Je peux donc compléter ma multiplication et j’obtiens:

\[\begin{array}{ccccccc}
1 & 2 & 3 & 4 & 5^5 & 6^5 & 7\\
\times & & & & & & 6 \\
& & & & & 1 & 2
\end{array}\]

En poursuivant, j’obtiens bien:

\[\begin{array}{ccccccc}
1^1 & 2^2 & 3^3 & 4^4 & 5^5 & 6^5 & 7\\
\times & & & & & & 6 \\
7 & 6 & 5 & 4 & 3 & 1 & 2
\end{array}\]

Notons que les retenues ont été indiquées: à partir du chiffre des « octaines au carré », la retenue est exactement égale au chiffre de sa colonne: cela est crucial dans ce que nous verrons plus tard.

Va-t'on casser trois pattes à un canard?

Revenons maintenant sur les rives du Rhône à la Barthelasse et retrouvons notre ami Johan.
Autant vous le dire tout de suite, Johan compte avec ses pieds ²J’ai bien dit avec et non comme. Ne confondons pas avec Filou.. C’est un batteur. Les batteurs sont appréciés pour leurs qualités rythmiques: ils ont l’habitude, lorsqu’il ne s’agit pas de rythme ternaire, de marquer « hun…deux…hun…deux » tout en frappant le sol de manière concomitante avec leur pied. Ce qui fait que lorsqu’il leur arrive de calculer, ils le font en base \(2\).

Le nombre constitué des chiffres {non-nuls} apparaissant en base \(2\), rangés dans l’ordre croissant est:
\[1\]
Il est remarquable qu’il coïncide avec celui formé des mêmes chiffres mais ordonnés dans le sens décroissant.

Si on le multiplie par \(2-2\), on obtient… quelque chose de peu intéressant. Autant oublier tout de suite cette expérience décevante.

Le cas de la base \(3\) est un peu plus probant. La quantité \(3-2\) vaut \(1\), et:
\[12 \times 1 = 12\]
On retrouve l’opiniâtre insistance de \(1\) à préserver son standing, ce qui généralise les observations antérieures pour les bases \(10\) et \(8\), mais où cette fois réduites à leur portion congrue.

En réalité, on peut tenter dans toutes les bases possibles, sauf pour la base \(2\); le phénomène observé par Rémi dans le cas de la base \(10\) restera toujours vrai, à savoir:

Pour tout entier \(n\) plus grand que \(3\), le résultat de la multiplication en base \(n\) par \(n-2\) du nombre dont les chiffres sont les entiers \(1\), \(2\), … , \(n-1\) écrits dans cet ordre de la gauche vers la droite, le résultat donc de cette multiplication est le nombre formé des mêmes chiffres mais cette fois écrits dans l’ordre inverse, à l’exception des deux derniers qui sont \(12\) et non \(21\).

Dans cette affirmation, la lettre \(n\) n’est pas une inconnue, car elle représente un entier supposé … connu! Mais tout simplement pas précisé, qu’on peut choisir arbitrairement, si ce n’est que \(1\) et \(2\) sont exclus. Par exemple, si on fait le choix \(n=11\), cet énoncé stipule qu’en base 11:
\[123456789A \times 9 = A987654312\]
où la lettre \(A\) désigne le nombre entier \(10\).

On mesure mieux la portée de cet énoncé en songeant au cas des
myriapodes, dont les capacités arithmétiques, ainsi que la patience, risquent fort d’être mis en défaut s’ils entreprennent de calculer sur leurs pattes pour vérifier le cas \(n=1000\): multiplier un nombre de \(1000\) chiffres, et où en outre chaque chiffre peut représenter un nombre de l’ordre du millier, est une tâche qui n’a rien de trivial !

Vous voulez des preuves?

Il est bien beau de faire des affirmations, toujours est-il, du moins en mathématiques, qu’il convient de les justifier. Il ne s’agit pas de vérifier notre énoncé en le testant sur tous les cas à envisager, puisque l’infinité des possibilités rend l’entreprise impossible, même pour le plus puissant ordinateur existant ou à venir!

Une première preuve consiste à se raccrocher à l’arsenal conceptuel usuel en mathématique, connu par les étudiants de Licence de mathématiques ayant validé leur première année. On réécrit l’affirmation sous une forme appropriée au calcul:

\[(n-2) \times [\sum_{k=0}^{n-2} (n-k-1)n^k] = n + 2 + \sum_{k=2}^{n-2} (k+1)n^k\]

La preuve ne devrait pas poser de problème particulier pour les initiés connaissant l’expression de la somme d’une série géométrique, mais pour les autres, les néophytes, contentons-nous d’indiquer que par exemple le terme \(\sum_{k=0}^{n-2} (n-k-1)n^k\) représente la somme de tous les nombres de la forme \((n-k-1)n^k\) où \(k\) prend toutes les valeurs entières comprises entre \(0\) et \(n-2\) (et où \(n\) représente l’entier sur lequel nous sommes en train de vérifier l’affirmation).

Mais autant dire que cette preuve est peu éclairante (surtout pour les non-initiés!) et fort peu élégante, tout comme une victoire aux pénalty du PSG. La formulation préparatoire au calcul est elle-même assez hideuse et a perdu tout l’attrait qu’avait donné Rémi lui-même.

Essayons un peu plus de finesse, et aussi de percevoir un peu mieux ce qui se passe, en tentant de comprendre ce qui se passe lorsqu’on applique la méthode de multiplication de deux nombres, bien connu de tous et de notre araignée, mais dans le cadre étendu d’une base \(n\) quelconque.

Commençons par poser le calcul:

\[\begin{array}{cccccccc}
1 & 2 & … & k & … & (n-3) & (n-2) & (n-1)\\
\times & & & & & & & (n-2)
\end{array}\]

Au vu du résultat escompté, le calcul des deux derniers chiffres du résultat devrait être spécial par rapport aux autres termes. Commençons donc par les effectuer à part.
Le chiffre des unités doit être obtenu en multipliant \((n-1)\) par \((n-2)\), puis en isolant le reste modulo \(n\), c’est à dire la quantité qui reste après avoir constituer autant de paquets à \(n\) éléments qu’il est possible de faire:

\[(n-1)\times (n-2) = n^2 -3n + 2 = (n-3)n + 2\]

On voit ainsi que le dernier chiffre du résultat de la multiplication, écrit en base \(n\), doit être \(2\). En outre, la retenue à reporter sur la seconde colonne (à partir de la droite) est \(n-3\). Donc:

\[\begin{array}{cccccccc}
1 & 2 & … & k & … & (n-3) & (n-2)^{(n-3)} & (n-1)\\
\times & & & & & & & (n-2)\\
& & & & & & & 2
\end{array}\]

Intéressons-nous au deuxième chiffre: c’est le reste modulo \(n\) de la multiplication de \((n-2)\) par lui-même, auquel on doit ajouter la retenue \(n-3\). Donc:

\[(n-2)\times(n-2) + n – 3 = n^2 -4n + 4 + n – 3 = n^2 -3n + 1 = (n-3)n + 1\]

Il s’agit donc de \(1\), comme espéré, et en outre, la retenue à reporter à la colonne suivante est \(n-3\).

Lorsque nous avions opéré le calcul dans le cas de la base \(8\), nous avions observé que la retenue à reporter à la colonne \(k\) (à partir de la gauche) est justement l’entier \(k\) lui-même, tant que \(k\) est plus petit que \(6\). Et si cela était vrai quelque soit l’entier \(n\) choisi? Pour résoudre notre problème, posons-nous une nouvelle question:

Est-il vrai que pour tous les entiers \(k\) plus petits que \(n-3\), la retenue à reporter à la colonne \(k\) est l’entier \(k\) lui-même? 

Ce que nous allons faire, c’est montrer que si cette propriété est vraie pour un entier \(k\), alors elle est aussi vrai pour l’entier \(k-1\). Sachant qu’elle est déjà vraie pour \(k = n-3\), on voit qu’elle doit alors être aussi vraie pour \(k=n-4\), puis \(k=n-5\), puis \(k=n-6\)… Elle se propagera automatiquement à tous les entiers plus petits que \(n-3\), jusqu’au cas \(k=1\).
C’est le type même de ce qu’on appelle une preuve par récurrence : au lieu de montrer la propriété pour chaque entier \(k\) un par un, ce qui pourrait vite devenir rébarbatif, on se contente de voir que la propriété se transmet bien entre entiers successifs, et la valide automatiquement, comme une file de dominos s’abattant les uns après les autres, pour peu que la bonne impulsion de départ ait bien lieu, ici la validité de l’affirmation pour \(k=n-3\).

Vérifions cette hérédité pour la colonne \(k\), en supposant donc que la retenue à y reporter soit \(k\). Le calcul à opérer consiste à multiplier \(k\) par \((n-2)\), à ajouter \(k\) (la retenue), et à chercher quel est le reste modulo \(n\) du résultat de ce calcul:

\[k\times (n-2) + k = kn – 2k + k = (k-1)n + n-k\]

Le reste est donc \(n-k\), mais surtout, la retenue à reporter à la colonne \(k-1\) est bien \(k-1\)! Nous avons bien réussi à montrer l’hérédité de notre affirmation, et donc sa véracité.

Notre intuition à propos des retenues étant maintenant confortée, nous savons que le calcul effectué ci-dessus sous l’hypothèse que la retenue est \(k\) n’est pas seulement une supposition, mais bel et bien le bon calcul à opérer! Ainsi, le \(k\)-ième chiffre à partir de la gauche du résultat final est \(n-k\), pour \(k\) plus petit que \(n-3\). Sous la forme habituelle est plus visuelle, nous avons obtenu:

 

\[\begin{array}{cccccccc}
1^1 & 2^2 & … & k^k & … & (n-3)^{(n-3)} & (n-2)^{(n-3)} & (n-1)\\
\times & & & & & & & (n-2)\\
(n-1) & (n-2) & … & (n-k) & … & 3 & 1 & 2
\end{array}\]

Et voilà. Nous connaissons un nouveau théorème: la curiosité de Rémi nous a donné un énoncé, que nous avons montré, et en cours de route, pour faire cette preuve, nous avons utilisé notre intuition pour subodorer la manière dont le calcul se passe, que nous avons pu
vérifier. Bel exemple, certes un poil élémentaire, de ce qu’est le travail de recherche en mathématiques…

Il y a bien sûr la question de la pertinence du théorème que nous venons de démontrer: va-t’il permettre de résoudre la faim dans le monde? Trouver le vaccin contre le virus H1N1? J’imagine que vous en doutez, et moi comme vous. Mais le fait que vous ayiez lu ce texte jusqu’à cette ligne met bien en évidence son intérêt, sans compter la joie ressentie par Rémi et qu’il a conservé en mémoire, au moins suffisament pour la transmettre un soir de juillet 2009, plusieurs années après sa découverte initiale.

Il y a aussi la pertinence mathématique: cette propriété est-elle une voie de départ supplémentaire pour explorer les nombreuses et fascinantes propriétés des nombres que l’humanité n’a cessé d’explorer depuis l’aube des temps? J’avoue l’ignorer, mais peut-être certains de mes collègues, plus experts en théorie des nombres, connaissent un élément de réponse et sauront y reconnaître une manifestation d’une notion arithmétique plus profonde…

Euh, c'est bien un Théorème de Rémi?

Ah, mais il y a une chose fondamentale que nous n’avons pas faite, et qui doit être le prélude à toute activité mathématique: ce que je cherche à démontrer est-il inédit, ou a t’il déjà été observé par quelqu’un auparavant?
Je vais me contenter cette fois-ci de googeliser « 123456789 x 8 » et de voir ce que cela donne.

On retrouve de multiples liens vers des sites où nombreux sont ceux qui s’enthousiasment sur les observations suivantes:

 

1 x 8 + 1 = 9

12 x 8 + 2 = 98

123 x 8 + 3 = 987

1234 x 8 + 4 = 9876

12345 x 8 + 5 = 98765

123456 x 8 + 6 = 987654

1234567 x 8 + 7 = 9876543

12345678 x 8 + 8 = 98765432

123456789 x 8 + 9 = 987654321

(On peut consulter par exemple: http://richardphillips.org.uk/number/Num8.htm )

La dernière ligne est une simple variation sur le Théorème de Rémi, vu que l’égalité \(12+9=21\) est une trivialité mentale. À vrai dire, notre preuve consiste justement à établir les premières égalités! Prenons par exemple la ligne:

12345 x 8 + 5 = 98765

Ce calcul n’est en fait qu’une portion du calcul plus général du produit de \(123456789\) par \(8\), celui produisant les \(5\) premiers chiffres du résultat. En effet, la seule ingérence du calcul sur les chiffres suivant dans cette partie initiale consiste en la valeur de la retenue à reporter à la cinquième colonne, qui est justement, comme nous l’avons montré, \(5\). Ainsi, la liste de calculs que nous avons reporté ici est essentiellement une explicitation du raisonnement que nous avons mené. Mais nous avons fait mieux, nous avons vu que le même phénomène reste vrai en toute base, et pas seulement dans la base \(10\).

Amis scolopendres, arrêtez donc vos calculs, et retournez plutôt goûter la douceur d’une nuitée provençale baignée par les rythmes tropicaux.