Prérequis
Résumé
Après avoir défini la notion d'inverse modulo $n$ et s'être penché sur le sujet, nous apprendrons comment résoudre une équation linéaire (modulo $n$) et ensuite un système de telles équations. Le théorème des restes chinois qui nous permettra de traiter ce dernier point est aussi essentiel d'un point de vue théorique et permet parfois la résolution de problèmes plus complexes.
Ce chapitre a été
écrit par N. Radu et
mis en ligne le 8 décembre 2014.
1. Notion d'inverse
Comme nous l'avons déjà mentionné, il n'est pas toujours permis de diviser les deux membres d'une égalité modulo $n$ par un nombre entier. Nous perdons par exemple l'égalité lorsque l'on divise les deux membres de l'expression $6 \equiv 16 \pmod{10}$ par $2$.
Il existe cependant certains cas où la division est permise. Pour trouver dans quels cas cela nous est permis, il nous faut revenir à la définition première de division. Lorsque nous travaillions sur les réels, nous savions que tout nombre non-nul admettait un inverse (pour tout $x \in \mathbb{R}_0$, il existe $y \in \mathbb{R}_0$ tel que $x\cdot y = 1$). Il nous était alors permis de diviser les deux membres d'une équation par $x$, puisque cela revenait à les multiplier par $y$. S'il nous était possible de diviser par les nombres $x$ non nuls, c'était en fait parce que chacun d'eux possédait un inverse.
Il est donc naturel de définir une notion d'inverse modulo $n$.
Dès lors, si $n$ est fixé et $x$ possède un inverse modulo $n$, il nous est autorisé de diviser les deux membres d'une égalité modulo $n$ par le nombre $x$ (puisque cela revient à multiplier chacun d'eux par $y$). Dans notre contre-exemple, $n$ était égal à $10$ et nous souhaitions diviser par $2$. Nous ne pouvions pas le faire car $2$ ne possède pas d'inverse modulo $10$. En effet, $2 \cdot y$ est toujours pair et ne saurait être égal à $1$ modulo $10$.
Existence d'inverse
Pour diviser par $x$, il suffit donc que $x$ possède un inverse modulo $n$. Le mieux serait donc de trouver un critère nous permettant de décider si $x$ possède un inverse modulo $n$ ou non. Il existe en fait un tel critère, dont la démonstration est preque immédiate grâce au théorème de Bézout :
Proposition (existence d'un inverse)
Le nombre $x$ possède un inverse modulo $n$ si et seulement si $(x, n) = 1$.
Démonstration
On a la suite d'équivalences suivante :
$$\begin{align}
& x \text{ possède un inverse modulo } n\\
\Leftrightarrow \ & \exists\ y \quad\text{tel que} \quad x\cdot y \equiv 1 \pmod n\\
\Leftrightarrow \ & \exists\ y \quad\text{tel que} \quad x\cdot y - 1 \quad \text{est divisible par } n\\
\Leftrightarrow \ & \exists\ y, k \quad\text{tels que} \quad x\cdot y - 1 = n\cdot k \\
\Leftrightarrow \ & \exists\ y, k \quad\text{tels que} \quad x\cdot y - n\cdot k = 1
\end{align} $$ Or, par le théorème de Bézout, de tels $y$ et $k$ existent si et seulement si $1$ est divisible par $(x, n)$. Autrement dit, on doit avoir $(x, n) = 1$ ce qui signifie que $x$ possède un inverse si et seulement si il est premier avec $n$.
Dans notre contre-exemple, on avait $(2,10) = 2 \neq 1$ et $2$ ne possédait donc pas d'inverse modulo $10$.
Construction de l'inverse
Dans notre contexte (pour diviser les deux membres d'une égalité), il n'est pas nécessaire de connaître l'inverse de $x$, il suffit de savoir qu'il existe. Cependant, il arrive que connaître l'inverse d'un nombre modulo $n$ soit utile, comme ce sera le cas pour résoudre des équations modulaires.
Pour le trouver, au vu de la démonstration concernant l'existence d'un inverse, il suffit de trouver des nombres $y$ et $k$ tels que $x\cdot y - n \cdot k = 1$. Cela se fait exactement comme nous cherchions les coefficients intervenant dans le théorème de Bézout (en remontant l'algorithme d'Euclide). Le nombre $y$ est alors l'inverse de $x$ modulo $n$ (en effet, vu que $n \cdot k \equiv 0 \pmod n$, on a $x\cdot y \equiv 1 \pmod n$)
Cherchons par exemple l'inverse de $17$ modulo $59$. On calcule d'abord $(17, 59)$ à l'aide de l'algorithme d'Euclide :
$$\begin{align}
59 &= 3\cdot 17 + 8 \\
17 &= 2 \cdot 8 + \boxed{1} \\
8 &= 8\cdot 1 + 0
\end{align}$$ On a donc $(17, 59) = 1$, ce qui signifie que $17$ possède bien un inverse modulo $59$. Pour le trouver, on remonte l'algorithme. On a :
$$\begin{align}
1 &= 17 - 2\cdot 8\\
&= 17 - 2\cdot(59 - 3\cdot 17)\\
&= 7\cdot 17 - 2\cdot 59
\end{align}$$ Et l'inverse de $17$ est donc $7$. On peut le vérifier aisément puisque $7\cdot 17 \equiv 119 \equiv 1 \pmod{59}$.
Unicité de l'inverse
L'inverse d'un nombre modulo $n$ ne semble a priori pas unique vu que nous avions remarqué que les coefficients intervenant dans le théorème de Bézout ne l'étaient pas. D'ailleurs, tous les nombres égaux à $7$ modulo $59$ sont également des inverses de $17$. Cela dit, n'oublions pas que nous travaillons modulo $n$. L'inverse d'un nombre est en fait bien unique modulo $n$ (c'est-à-dire que parmi les nombres entre $0$ et $58$, seul $7$ est inverse de $17$ modulo $59$).
Proposition (unicité de l'inverse)
Si $x$ possède un inverse modulo $n$, alors cet inverse est unique modulo $n$.
Démonstration
Si $y_1$ et $y_2$ sont des inverses de $x$ modulo $n$, alors par définition on a
$$ x \cdot y_1 \equiv 1 \equiv x \cdot y_2 \pmod n.$$ Mais nous pouvons à présent diviser les deux membres extrêmes de l'égalité par $x$ puisque celui-ci possède un inverse modulo $n$, d'où
$$ y_1 \equiv y_2 \pmod n.$$
2. Équation linéaire
Penchons-nous à présent sur la résolution de l'équation
$$a x \equiv b \pmod n$$ où $a, n \in \mathbb{Z}_0$ et $b \in \mathbb{Z}$ sont fixés alors que $x$ est l'inconnue.
Le cas où $(a, n) = 1$
Si $a$ et $n$ sont premiers entre eux, alors $a$ possède un inverse modulo $n$, comme nous l'avons-vu dans le point théorique précédent.
Nous notons $a^{-1}$ cet inverse et pouvons donc multiplier les deux membres de l'égalité par $a^{-1}$ pour obtenir l'équation équivalente
$$ x \equiv a^{-1}b \pmod n$$ qui nous donne donc immédiatement la solution à notre équation de départ : il s'agit des $x$ congrus à $a^{-1}b$ modulo $n$.
Le cas où $(a, n) \neq 1$
Si $a$ et $n$ ne sont pas premiers entre eux, on note $(a, n) = d \neq 1$. Vu que $d$ divise $a$ et $n$, on peut poser $a = d\cdot a'$ et $n = d\cdot n'$. On a alors $(a', n') = 1$ puisque nous avons divisé $a$ et $n$ par tous les facteurs communs qu'ils avaient.
Deux cas se présentent alors :
- Si $b$ n'est pas divisible par $d$, alors il n'y a aucune chance de trouver un $x$ tel que $ax - b$ soit divisible par $n$, puisqu'il n'est en particulier pas divisible par $d$. Dans ce cas, l'équation ne possède pas de solution.
- Si $b$ est divisible par $d$, alors on pose $b = d \cdot b'$ et l'équation se réécrit
$$da' x \equiv d b' \pmod{d n'}.$$ Or, $d a' x - d b'$ est divisible par $d n'$ si et seulement si $a' x - b'$ est divisible par $n'$, ce qui nous permet de simplifier tous les $d$ pour nous ramener à
$$ a' x \equiv b' \pmod{n'}.$$
Vu que $(a', n') = 1$, nous nous sommes ramenés au premier cas et pouvons multiplier les deux membres par l'inverse $a'^{-1}$ de $a'$ modulo $n'$ pour trouver
$$x \equiv a'^{-1} b' \pmod {n'}$$ ce qui signifie que la solution est donnée par les $x$ congrus à $a'^{-1} b'$ modulo $n'$.
Exemples
- Considérons l'équation
$$4x \equiv 2 \pmod {7}.$$ Vu que $(4,7) = 1$, nous sommes dans le premier cas. On cherche alors l'inverse de $4$ modulo $7$. On peut utiliser l'algorithme d'Euclide mais il est ici aisé de remarquer qu'il s'agit de $2$ vu que $4\cdot 2 \equiv 8 \equiv 1 \pmod 7$. On multiplie alors les deux membres par $2$ et on obtient
$$x \equiv 4 \pmod 7.$$ L'ensemble des solutions est donc l'ensemble des $x$ congrus à $4$ modulo $7$ : $x \in \left\{\dots, -10, -3, 4, 11, \dots \right\}$.
- Considérons l'équation
$$ 6x \equiv 9 \pmod{15}.$$ Ici, $(6,15) = 3$. Mais $b = 9$ est également divisible par $3$, donc nous pouvons diviser les trois nombres par $3$ pour nous ramener à
$$ 2x \equiv 3 \pmod 5.$$ On procède alors comme précédemment, en multipliant les deux termes par $3$, l'inverse de $2$ modulo $5$ :
$$ x \equiv 9 \equiv 4 \pmod 5.$$ L'ensemble des solutions est donc l'ensemble des $x$ congrus à $4$ modulo $5$.
- Considérons l'équation
$$ 4x \equiv 5 \pmod{14}.$$ Ici, $(4,14) = 2$. Mais $b = 5$ n'est pas divisible par $2$, et il n'y a donc aucune solution à cette équation.
3. Système d'équations
Maintenant que nous savons résoudre une équation linéaire, nous sommes en droit de nous demander comment résoudre un système de plusieurs équations linéaires. Nous verrons dans le point théorique suivant un théorème qui s'intéresse à de tels systèmes, mais pour s'en faire une intuition nous allons d'abord observer un exemple.
Solution
Soit $x$ le nombre de billes de Jean. Les conditions de l'énoncé se réécrivent simplement comme un système d'équations :
$$\left\{ \begin{align}
x &\equiv 1 \pmod 2 \\
x &\equiv 2 \pmod 3 \\
x &\equiv 4 \pmod 7 \\
\end{align}\right.$$ Il ne semble a priori pas simple de trouver une solution à ce système : par où commencer ? Au lieu de nous attaquer directement à celui-ci, nous allons commencer par essayer de résoudre un système plus simple. Nous gardons les modulos $2$, $3$ et $7$, mais remplaçons les valeurs $1$, $2$ et $4$ par $1$, $0$ et $0$ respectivement (pour n'avoir que des zéros excepté un $1$). On cherche donc une solution $x_1$ au système simplifié :
$$\left\{ \begin{align}
x_1 &\equiv 1 \pmod 2 \\
x_1 &\equiv 0 \pmod 3 \\
x_1 &\equiv 0 \pmod 7 \\
\end{align}\right.$$ Les deux dernières équations de ce système sont faciles à exploiter, puisqu'elles demandent que $x_1$ soit divisible par $3$ et par $7$, c'est-à-dire par $21$. On peut donc poser $x_1 = 21y_1$ avec $y_1 \in \mathbb Z$, et la seule équation qu'il nous reste est alors
$$21y_1 \equiv 1 \pmod 2\\
\Leftrightarrow y_1 \equiv 1 \pmod 2$$ Une solution est donc simplement $y_1 = 1$, qui donne $x_1 = 21\cdot 1 = 21$. On peut bien vérifier que $x_1 = 21$ est congru à $1$ modulo $2$, et à $0$ modulo $3$ et $7$.
Nous répétons dorénavant la même procédure, mais en remplaçant les valeurs de droites par $0$, $1$ et $0$. On cherche donc une solution $x_2$ au deuxième système :
$$\left\{ \begin{align}
x_2 &\equiv 0 \pmod 2 \\
x_2 &\equiv 1 \pmod 3 \\
x_2 &\equiv 0 \pmod 7 \\
\end{align}\right.$$ La première et la troisième équation nous indiquent que $x_2$ doit être divisible par $2$ et par $7$, ce qui nous permet de poser $x_2 = 14y_2$. Et la deuxième équation devient alors
$$14y_2 \equiv 1 \pmod 3\\
\Leftrightarrow 2 y_2 \equiv 1 \pmod 3$$ Il s'agit d'une simple équation linéaire, que nous avons appris à résoudre. Il suffit de multiplier les deux membres par l'inverse de $2$ modulo $3$, qui se trouve être $2$, pour obtenir $y_2 \equiv 2 \pmod 3$. Une solution est donc $y_2 = 2$, qui donne $x_2 = 14\cdot 2 = 28$.
On termine avec un troisième système, en utilisant cette fois $0$, $0$ et $1$ pour valeurs à droites :
$$\left\{ \begin{align}
x_3 &\equiv 0 \pmod 2 \\
x_3 &\equiv 0 \pmod 3 \\
x_3 &\equiv 1 \pmod 7 \\
\end{align}\right.$$ Les deux premières équations donnent $x_3$ divisible par $2$ et par $3$, donc on peut poser $x_3 = 6y_3$. La dernière équation devient alors :
$$6y_3 \equiv 1 \pmod 7$$ Il nous faut cette fois multiplier par l'inverse de $6$ modulo $7$, qui est $6$, pour obtenir $y_3 \equiv 6 \pmod 7$. Une solution est donc donnée par $y_3 = 6$, qui donne $x_3 = 6\cdot 6 = 36$.
Nous avons résolu trois systèmes plus simples que le système initial, et avons trouvé $x_1 = 21$, $x_2 = 28$ et $x_3 = 36$ comme solutions. Très bien, mais en quoi cela nous aide-t-il ? Rappelons que l'on cherche un nombre $x$ vérifiant
$$\left\{ \begin{align}
x &\equiv 1 \pmod 2 \\
x &\equiv 2 \pmod 3 \\
x &\equiv 4 \pmod 7 \\
\end{align}\right.$$ Il suffit en fait de se rendre compte que nos nombres $x_1$, $x_2$ et $x_3$ ont été construits de sorte que $x_1$ est le seul des trois à être non-nul modulo $2$. Et en plus, il vaut $1$ modulo $2$. De la même façon, $x_2$ est le seul à être non-nul modulo $3$, et il vaut $1$ modulo $3$. Enfin, $x_3$ est le seul à être non-nul modulo $7$, et il vaut $1$ modulo $7$. Cela signifie qu'en choisissant
$$x = 1 \cdot x_1 + 2 \cdot x_2 + 4 \cdot x_3$$ on obtient un nombre qui vaut $1$ modulo $2$, $2$ modulo $3$, et $4$ modulo $7$, comme voulu ! Nous trouvons donc
$$x = 1 \cdot 21 + 2 \cdot 28 + 4 \cdot 36 = 221$$ Il se peut donc que Jean possède $221$ billes. Notons toutefois qu'il ne s'agit que d'une solution particulière, et il n'y a même aucune raison que ce soit la plus petite. En fait, on remarque qu'en rajoutant (ou soustrayant) un multiple de $2\cdot3\cdot 7 = 42$ à notre solution $221$, ses valeurs modulo $2$, $3$ et $7$ ne vont pas changer. Autrement dit, toutes les nombres congrus à $221$ modulo $42$ sont solutions, c'est-à-dire tous les nombres congrus à $11$ modulo $42$.
Mais s'agit-il des seules solutions ? Pour le voir, supposons avoir deux solutions $x$ et $x'$ de notre système initial. On s'aperçoit alors que $x-x'$ doit être congru à $0$ modulo $2$, $3$ et $7$, c'est-à-dire que $x-x'$ doit être divisible par $2$, $3$ et $7$, et donc par $42$. Autrement dit, $x$ et $x'$ doivent être égaux modulo $42$. Cela signifie que deux solutions à notre système sont toujours égales modulo $42$. On a donc bien montré que les solutions sont exactement les nombres $x$ égaux à $11$ modulo $42$.
4. Théorème des restes chinois
Nous venons de voir un exemple de système d'équations linéaires. Ce n'était qu'un exemple, mais la démarche que nous avons suivie pour le résoudre est en fait tout à fait générale ! Nous sommes donc en mesure de démontrer le théorème suivant :
Théorème des restes chinois
Si $n_1, n_2, \dots, n_k$ sont des nombres premiers entre eux deux à deux, et si $a_1, a_2, \dots, a_k \in \mathbb Z$, alors il existe un unique $x$ modulo $n_1\cdot \ldots \cdot n_k$ tel que
$$\left\{ \begin{align}
x &\equiv a_1 \pmod {n_1} \\
x &\equiv a_2 \pmod {n_2} \\
&\vdots \\
x &\equiv a_k \pmod {n_k} \\
\end{align}\right.$$
Nous avons déjà démontré ce théorème sur le cas particulier des billes de Jean, où $k = 3$, $n_1 = 2$, $n_2 = 3$, $n_3 = 7$, $a_1 = 1$, $a_2 = 2$ et $a_3 = 4$. Nous avons en effet vu qu'il existait une unique solution modulo $2\cdot 3\cdot 7 = 42$. Et nous avons même vu comment construire cette solution.
Le théorème des restes chinois se démontre en suivant exactement les mêmes étapes que celles que nous avons suivies pour le problème des billes.
Démonstration
- Montrons l'existence. Cherchons d'abord une solution au système plus simple (d'inconnue $x_1$)
$$\left\{ \begin{align}
x_1 &\equiv 1 \pmod {n_1} \\
x_1 &\equiv 0 \pmod {n_2} \\
&\vdots \\
x_1 &\equiv 0 \pmod {n_k} \\
\end{align}\right.$$ Un $x_1$ solution du système doit avant tout être multiple de $n_2, n_3, \dots, n_k$, et donc de leur produit $n_2\cdot n_3 \cdot \ldots \cdot n_k$ vu qu'ils sont premiers entre eux.
On peut donc noter $x_1 = n_2\cdot n_3 \cdot \ldots \cdot n_k \cdot y_1$ et chercher $y_1$ tel que
$$n_2\cdot n_3 \cdot \ldots \cdot n_k \cdot y_1 \equiv 1 \pmod {n_1}.$$ Il s'agit d'une simple équation linéaire, dont on trouve la solution en multipliant par l'inverse $a$ de $n_2\cdot n_3 \cdot \ldots \cdot n_k$ modulo $n_1$ :
$$y_1 \equiv a \pmod {n_1}.$$ Une solution $x_1$ au système simplifié est donc donnée par $x_1 = n_2\cdot n_3 \cdot \ldots \cdot n_k \cdot a$, où $a$ est l'inverse de $n_2\cdot n_3 \cdot \ldots \cdot n_k$ modulo $n_1$.
De la même façon, on peut pour chaque $i \in \left\{1, \dots, k\right\}$ trouver un $x_i$ solution du système
$$\left\{ \begin{align}
x_i &\equiv 0 \pmod {n_1} \\
x_i &\equiv 0 \pmod {n_2} \\
&\vdots \\
x_i &\equiv 1 \pmod {n_i} \\
&\vdots \\
x_i &\equiv 0 \pmod {n_k} \\
\end{align}\right.$$ (avec un $1$ uniquement sur la $i$-ème ligne).
Il ne reste alors plus qu'à considérer le nombre $x = a_1 \cdot x_1 + \ldots + a_k \cdot x_k$, dont on vérifie qu'il vaut $a_i$ modulo $n_i$ pour tout $i \in \{1, \ldots, k\}$. C'est bien une solution de notre système initial.
- Montrons à présent l'unicité. Si $x$ et $x'$ vérifient tous les deux le système d'équations, alors on remarque que $x-x'$ vérifie
$$\left\{ \begin{align}
x - x' &\equiv 0 \pmod {n_1} \\
x - x' &\equiv 0 \pmod {n_2} \\
&\vdots \\
x - x' &\equiv 0 \pmod {n_k} \\
\end{align}\right.$$ ce qui signifie que $x-x' \equiv 0 \pmod {n_1 \cdot \ldots \cdot n_k}$, c'est-à-dire que $x$ et $x'$ sont égaux modulo $n_1 \cdot \ldots \cdot n_k$, d'où l'unicité annoncée.
Remarques
- En présence d'un système où des coefficients apparaissent devant $x$ sur certaines lignes (comme $5x \equiv 1 \pmod 7$), il semble à première vue que le théorème n'est pas applicable. Rappelons-nous cependant qu'une équation du type $ax \equiv b \pmod n$ est une simple équation linéaire qui peut être transformée en $x \equiv ba^{-1} \pmod n$, pourvu que $a$ possède un inverse $a^{-1}$ modulo $n$. On peut donc faire disparaître les éventuels coefficients devant $x$, pour se ramener à une situation où le théorème des restes chinois peut être utilisé. Par exemple, $5x \equiv 1 \pmod 7$ se transforme simplement en $x \equiv 3 \pmod 7$.
- Il se peut aussi que l'on soit dans un cas où les nombres $n_1, \dots, n_k$ ne sont pas premiers entre eux deux à deux. Il est toutefois toujours possible de se ramener à un système de ce type. Par exemple, si on considère le système
$$\left\{ \begin{align}
x &\equiv 13 \pmod {18} \\
x &\equiv 11 \pmod {12} \\
\end{align}\right.$$ il nous suffit de séparer le modulo $18$ en un modulo $2$ et un modulo $9$, ainsi que le modulo $12$ en un modulo $4$ et un modulo $3$, pour obtenir :
$$\left\{ \begin{align}
x &\equiv 13 \equiv 1 \pmod {2} \\
x &\equiv 13 \equiv 4 \pmod {9} \\
x &\equiv 11 \equiv 3 \pmod {4} \\
x &\equiv 11 \equiv 2 \pmod {3} \\
\end{align}\right.$$ On constate sur cet exemple que l'équation modulo $4$ est plus forte que l'équation modulo $2$, vu qu'un nombre congru à $3$ modulo $4$ est toujours congru à $3 \equiv 1$ modulo $2$. On peut donc laisser tomber l'équation modulo $2$. Par contre on remarque aussi que l'équation modulo $9$ contredit l'équation modulo $3$, vu qu'un nombre congru à $4$ modulo $9$ est toujours congru à $4 \equiv 1$ modulo $3$, et non à $2$. Vu que ces deux équations se contredisent, le système n'a pas de solution.
De manière générale, toute équation du type $x \equiv a \pmod {p_1^{e_1} p_2^{e_2} \ldots p_m^{e_m}}$ peut être remplacée (grâce au théorème des restes chinois) par les $m$ équations
$$\left\{ \begin{align}
x &\equiv a \pmod {p_1^{e_1}} \\
x &\equiv a \pmod {p_2^{e_2}} \\
& \ \ \vdots\\
x &\equiv a \pmod {p_m^{e_m}} \\
\end{align}\right.$$ Si l'on part d'un système où les nombres $n_1, \ldots, n_k$ ne sont pas premiers entre eux, on peut donc toujours utiliser la décomposition en facteurs premiers de chacun des $n_i$ pour se ramener à un système d'équations dont les modulos sont tous des puissances de nombres premiers. On obtient alors, pour certains $p$, plusieurs équations modulo une puissance de $p$. Il y a deux cas de figure pour chacun de ceux-ci :
- Soit ces équations se contredisent (comme c'était le cas avec les équations modulo $3$ et $9$ ci-dessus), auquel cas le système n'a pas de solution ;
- Soit l'équation avec le plus grand modulo est plus forte que toutes les autres (comme c'était le cas avec les équations modulo $2$ et $4$ ci-dessus), auquel cas on peut garder l'équation la plus forte uniquement.
À la fin de ce processus, soit on a trouvé une contradiction, soit il nous reste des équations dont les modulos sont des puissances de nombres premiers deux à deux distincts et on peut enfin appliquer le théorème des restes chinois.
- Dans les problèmes un peu avancés, c'est surtout l'existence d'une solution qui est primordiale et il est rare qu'il soit nécessaire de connaître sa construction. Il n'est cependant pas compliqué de retenir la démarche à suivre, à savoir résoudre d'abord les systèmes simplifiés.
5. Exemples concrets
Il existe beaucoup d'exemples de problèmes dont la résolution est un appel direct au théorème des restes chinois. C'est d'ailleurs car ce type de problème apparaît assez naturellement que les mathématiciens se sont attachés à leur trouver une solution générale.
L'armée de Han Xin
On associe parfois le problème résolu par le théorème au général chinois Han Xin comptant son armée. Celle-ci étant gigantesque, en compter les membres un par un ne semblait pas envisageable. Pour remédier à cela, une solution est donc de demander aux militaires de se placer en rangs de différentes façons et d'observer le nombre d'hommes qui n'ont pas pu se ranger. Le problème peut donc se voir par exemple de la sorte :
Solution
On cherche ici un nombre entier $x$ compris entre $0$ et $300\,000$ respectant les conditions :
$$\left\{\begin{align}
x &\equiv 2 \pmod 5 \\
x &\equiv 3 \pmod 7 \\
x &\equiv 6 \pmod 8 \\
x &\equiv 1 \pmod 9 \\
x &\equiv 0 \pmod {11} \\
x &\equiv 8 \pmod {13}
\end{align}\right.$$ Comme les nombres $5, 7, 8, 9, 11, 13$ sont premiers entre eux deux à deux, le théorème des restes chinois nous indique qu'il existe une unique solution modulo $5\cdot7\cdot8\cdot9\cdot11\cdot13 = 360\,360$. Avec un peu de courage, on peut trouver en suivant la méthode expliquée précédemment que l'armée de Han Xin compte dans notre exemple exactement $254\,782$ soldats.
Concordance de calendriers
On pense aussi que l'astronomie est une autre motivation des Chinois à résoudre ce genre de problème. En effet, on est vite amené à se poser des questions du type :
Solution
Le problème peut se réécrire (en oubliant les années bissextiles)
$$\left\{\begin{align}
x &\equiv -29 \pmod{365}\\
x &\equiv 2 \pmod{28}
\end{align}\right.$$ où $x$ est le nombre de jours qu'il faudra attendre avant d'observer un tel phénomène. En effet, il y a eu un nouvel an il y a $29$ jours, et ceux-ci se répètent tous les $365$ jours. De la même façon, il y aura une pleine lune dans deux jours et celles-ci se produisent tous les $28$ jours. Pour cet exemple, on trouve $x = 1066$ ce qui signifie que l'on observera une pleine lune le jour du nouvel an dans un peu moins de $3$ ans.
Le butin des pirates
Un autre exemple type, bien que plus anecdotique, est le suivant (merci Wikipédia pour l'énoncé).
Solution
Si $x$ désigne le nombre de pièces que comporte le trésor, le problème s'écrit cette fois-ci :
$$\left\{\begin{align}
x &\equiv 3 \pmod {17}\\
x &\equiv 4 \pmod {11}\\
x &\equiv 5 \pmod 6
\end{align}\right.$$ À nouveau, on peut utiliser le théorème des restes chinois et trouver $x = 785$ comme unique solution modulo $6\cdot11\cdot17 = 1122$. Le cuisinier peut donc espérer au moins $785$ pièces en commettant son crime...