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 $x$ est le nombre de sushis commandés par ce client, alors

$\begin{cases} x \equiv 3 \, [4] \\x \equiv 5 \, [9] \end{cases}$

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

$\begin{cases} x = 4 k_1 + 3 \quad & (L1) \\ x = 9 k_2 + 5 \quad &(L2) \end{cases}$

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 $x$ . 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:

$(-2 \times 4) + (1 \times 9) = 1$

Afin de combiner astucieusement les équations (L1) et (L2), on va multiplier (L1) par $(1\times 9)$ et (L2) par $(-2 \times 4)$ :

$\begin{cases} (1 \times 9) x = (1\times 9) \times 4 k_1 + (1 \times 9) \times 3 \quad & (L1) \\ (-2 \times 4) x = (-2 \times 4) \times 9 k_2 + (-2 \times 4) \times 5 \quad & (L2) \end{cases}$

c’est-à-dire:

$\begin{cases} 9 x = 36 k_1 + 27 \\ -8 x = -2 \times 36 k_2 - 40 \end{cases}$

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

$x = 36 (k_1 - 2 k_2) - 13$

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

$\exists K \in \mathbb{Z}, x = 36 K - 13$

Une autre façon d’écrire cela est $x \equiv -13 \, [36]$ . Comme $-13 \equiv 23 \, [36]$ , nous voyons donc que le nombre $x$ 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 $x=239$ . 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 $m$ et $n$ sont deux entiers premiers entre eux, et si $a$ et $b$ sont deux entiers alors le système:

$\begin{cases} x \equiv a \, [m] \\ x \equiv b \, [ n] \end{cases}$

possède une unique solution modulo $mn$ . Dans l’exemple des sushis, le système possédait une unique solution modulo 36, ce qui voulait dire que tous les nombres $x$ 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:

$\exists k_1, k_2 \in \mathbb{Z}, \begin{cases} x = m k_1 + a \quad & (L1) \\ x = n k_2 + b \quad &(L2) \end{cases}$

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

$(mu) + (nv) = 1$

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

$\exists k_1, k_2\begin{cases} (nv)x = (nv)m k_1 + (nv)a \quad & (L1) \\ (mu)x = (mu)n k_2 + (mu)b \quad &(L2) \end{cases}$

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

$(nv + mu)x = mn(v k_1 + uk_2) + nva + mub$

ce qui donne encore:

$x = mn(vk_1 + uk_2) + nva + mub$

Ainsi, nous voyons que si $x$ est solution alors $x \equiv nva + mub \, [mn]$ , ce qui veut bien dire que $x$ est unique modulo $mn$ .

Réciproquement, il s’agit de montrer que si $x \equiv nva + mub \, [mn]$ alors $x$ vérifie le système de départ. Tout d’abord remarquons que, puisque $mu + nv =1$ alors $nv = 1 - mu$ . Ainsi quand on regarde modulo $m$ , on a:

$x \equiv nva + mub \equiv nva \equiv (1-mu)a = a - mua \equiv a \, [m]$

Nous avons bien prouvé que $x \equiv a \, [m]$ . De la même façon, on prouve que $x \equiv b \, [n]$ en utilisant le fait que $mu = 1 - nv$ :

$x \equiv nva + mub \equiv mub \equiv (1-nv)b = b - nvb \equiv b \, [n]$

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 $\mathbb{Z} / mn \mathbb{Z}$ et $\mathbb{Z}/m \mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ sont isomorphes

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

$\begin{cases} x \equiv 3 \, [4] \\ x \equiv 5 \, [ 9] \end{cases}$

C’est sûr que de savoir qu’il existe un isomorphisme entre $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/9\mathbb{Z}$ et $\mathbb{Z}/36 \mathbb{Z}$ , ç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.

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

Anonyme dit :

5 octobre 2014 à 18 h 31 min

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

Réponse
- blogdemaths dit :
  
  5 octobre 2014 à 18 h 53 min
  
  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
  
  Réponse
  - Pierre Lecomte dit :
    
    5 octobre 2014 à 20 h 14 min
    
    Oh que c’est bien vrai! 😉
    
    J’aimeJ’aime
    
    Réponse
- Kikoo Lol dit :
  
  22 octobre 2014 à 19 h 46 min
  
  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
  
  Réponse
Ping : Le théorème de Wilson | Blogdemaths
Anonyme dit :

12 janvier 2019 à 15 h 54 min

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

Réponse
- blogdemaths dit :
  
  22 janvier 2019 à 19 h 53 min
  
  Merci à vous !
  
  J’aimeJ’aime
  
  Réponse
Pendice Leye dit :

27 avril 2019 à 18 h 16 min

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

Réponse
Patrick dit :

20 novembre 2020 à 22 h 45 min

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

Réponse