Le théorème des restes Chinois… avec des sushis

Quoi de plus logique que d’illustrer le théorème des restes Chinois avec un plat typiquement Japonais ?

Un restaurant Japonais propose la livraison de sushis. Pour ranger ces sushis, ce restaurant dispose de deux types de boîtes: des boites de 4 et des boites de 9.

Un client vient d’appeler et a commandé, pour un banquet, un certain nombre de sushis. Quand on range ces sushis uniquement dans des boites de 4, on s’aperçoit qu’après avoir rempli le plus de boîtes possibles, il en reste 3. Quand on range ces sushis uniquement dans des boites de 9, on constate qu’il en reste au final 5.

Sachant que ce client a commandé entre 210 et 270 sushis, combien ce client a-t-il commandé de sushis ?

Faut que j’arrête d’écrire des articles qui parlent de bouffe…

Sushi style

Ce problème s’interprète en termes de congruences de la façon suivante: si est le nombre de sushis commandés par ce client, alors

Plus simplement, pour ceux ne sont pas à l’aise avec les congruences, cela veut dire qu’il existe deux entiers et tels que:

L’équation (L1) traduit le fait que quand on remplit des boîtes de 4, il reste 3 sushis et (L2) traduit le fait que quand on remplit des boites de 9, il en reste 5.

Pour, résoudre ce système, l’idée serait de pouvoir combiner ces deux équations de façon à obtenir une seule équation donnant . Pour effectuer cette combinaison, on va utiliser une relation liant 4 et 9; comme on le sait, 4 et 9 sont premiers entre eux, ce qui se traduit par la relation de Bézout suivante:

Afin de combiner astucieusement les équations (L1) et (L2), on va multiplier (L1) par et (L2) par :

c’est-à-dire:

Pour finir, on ajoute la première ligne et la deuxième, ce qui donne:

On voit donc que les choses se sont grandement simplifiées puisque cette dernière égalité se traduit par:

Une autre façon d’écrire cela est . Comme , nous voyons donc que le nombre de sushis a pour reste 23 si on le divise par 36. On peut interpréter cela en disant que si on rangeait tous les sushis commandés par le client dans des boites de 36, alors il en resterait 23 à la fin.

Pour finir de répondre au problème, il faut se souvenir que le nombre de sushis est compris entre 210 et 270. Pour trouver le nombre exact de sushis, on ajoute autant de fois 36 à 23 jusqu’à arriver entre 210 et 270. Voici les nombres obtenus quand on ajoute successivement 36 en partant de 23 :

23, 59, 95, 131, 167, 203, 239, 275, …

La seule valeur comprise entre 210 et 270 est . Notre client a donc commandé 239 sushis (!) et on peut facilement vérifier que si on divise 239 par 4, il reste bien 3 et que si on divise 239 en 9, il reste bien 5.

Cas général

Je vous propose de démontrer le théorème des restes Chinois dans le cas général, en s’inspirant de ce qu’on vient de faire dans le cas pratique précédent.

Rappelons au préalable l’énoncé du théorème des restes Chinois: si et sont deux entiers premiers entre eux, et si et sont deux entiers alors le système:

possède une unique solution modulo . Dans l’exemple des sushis, le système possédait une unique solution modulo 36, ce qui voulait dire que tous les nombres solutions différaient d’un multiple de 36 (23, 59, 95, 131, 167, 203, 239, 275, …)

Commençons la démonstration. Le système précédent s’écrit sous la forme:

Pour combiner les lignes (L1) et (L2), on utilise le fait que et sont premiers entre eux: d’après le théorème de Bézout, il existe alors deux entiers tels que

Ensuite, on multiple (L1) par et on multiplie (L2) par :

Enfin, on ajoute ces deux lignes, ce qui donne:

ce qui donne encore:

Ainsi, nous voyons que si est solution alors , ce qui veut bien dire que est unique modulo .

Réciproquement, il s’agit de montrer que si alors vérifie le système de départ. Tout d’abord remarquons que, puisque alors . Ainsi quand on regarde modulo , on a:

Nous avons bien prouvé que . De la même façon, on prouve que en utilisant le fait que :

CQFD!

Bilan

Comme vous le voyez la démonstration que nous venons de faire du théorème Chinois est exactement le raisonnement qu’on avait utilisé en pratique lors de la résolution du problème sur les sushis. J’ai donc aussi voulu écrire cet article car je suis toujours étonné du nombre de gens (dont moi à une époque !) qui connaissent l’énoncé abstrait du théorème Chinois:

Les anneaux et sont isomorphes

mais qui ne sont pas capables de trouver en pratique les solutions d’un système particulier comme le suivant:

C’est sûr que de savoir qu’il existe un isomorphisme entre et , ça n’aide pas des masses à trouver les solutions !

Note:

• L’image est extraite de la page Wikipédia sur les sushis.
• Pour un problème un peu différent, avec des boites de nuggets au lieu de sushis (changement radical de culture culinaire !), voir cet article que j’avais écrit, où l’on trouve le nombre maximal de nuggets qu’on ne peut pas servir en remplissant des boites de 4, 6 ou 9 pièces.