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...

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.
Publicités
Cet article, publié dans Arithmétique, est tagué , , , , , . Ajoutez ce permalien à vos favoris.

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

  1. Anonyme dit :

    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.

    • blogdemaths dit :

      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.

    • Kikoo Lol dit :

      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.

  2. Ping : Le théorème de Wilson | Blogdemaths

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s