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 ?
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.
Un gros souci des maths post BAC : les énoncés généraux anas algorithme ! Par exemple, j’ai appris tardivement à inverser une matrice 4*4 à la main et sans trop d’effort.
J’aimeJ’aime
Tout à fait ! D’autant plus que c’est par la pratique qu’on apprend à faire des maths. On peut connaître tous les théorèmes que l’on veut, tant qu’on ne s’est pas confronté à les appliquer, on ne peut pas dire qu’on les maîtrise.
J’aimeJ’aime
Oh que c’est bien vrai! 😉
J’aimeJ’aime
C’est malheureusement aussi le cas en pré-bac. Je connais des élèves de prépa qui n’ont jamais fait un calcul à la main depuis la sixième. L’introduction des matrices (d’ordre 2) en terminale se solde par des calculs numériques à la calculatrice.
J’aimeJ’aime
Ping : Le théorème de Wilson | Blogdemaths
Merci beaucoup. Vous m’avez éclairé sur ce théorème. Il me reste encore à généraliser pour un système de plusieurs équations 🙂
J’aimeJ’aime
Merci à vous !
J’aimeJ’aime
Merci pour le raisonnement.
J’ai résolu ce problème avec une méthode différente de la votre et trouvé x=239. J’ai alors fouillé google pour avoir la certitude que j’ai trouvé juste. Je suis tombé sur ceci.
J’aimeAimé par 1 personne
Je crains qu’il y ait une confusion entre le théorème des restes chinois et le théorème chinois.
Le théorème chinois établit l’existence d’un isomorphisme h entre Z/pqZ et Z/pZ x Z/qZ pour p et q étrangers. Ce résultat qui vous a sûrement été enseigné en première année est très utile, même s’il reste inefficace pour les problèmes culinaires.
Par contre, la recherche de la bijection réciproque de h, est bien appelé le théorème des restes chinois, y compris dans des anneaux plus abstraits.
Cordialement.
J’aimeJ’aime