Théorie > Théorie des nombres > Équations modulaires

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 à mutliplier 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 :



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

Penchons-nous à présent sur la résolution de l'équation
$$a x \equiv b \pmod n$$ où $a, b \in \mathbb{Z}_0$ et $n \in \mathbb{N}_0$ 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 noter $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$ 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

1. 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\}$.
   


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


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

Maintenant que nous savons résoudre une simple équation, nous sommes en droit de nous demander comment résoudre un système de plusieurs équations. En utilisant le point théorique précédent, nous pouvons les résoudre une par une pour (si elles admettent toutes une solution) nous ramener à un système du type
$$\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.$$

Exemple

Un exemple populaire de tel système est le problème suivant.


Ce problème se réécrit facilement en un système d'équation. Si on note $x$ le nombre de billes, alors nous savons que
$$\left\{ \begin{align}
x &\equiv 1 \pmod {2} \\
x &\equiv 0 \pmod {3} \\
x &\equiv 2 \pmod {5} \\
\end{align}\right.$$ Il n'est a priori pas évident qu'il existe bel et bien une solution à ce problème, et encore moins de la trouver. Le théorème des restes chinois va, sous quelques conditions, nous assurer l'existence et l'unicité de la solution d'un tel système.

Énoncé

Le théorème des restes chinois s'énonce en toute généralité comme suit.


Le théorème fournit également une façon de construire $x$, mais nous allons la découvrir dans la preuve de l'existence de la solution.

Remarques

1. Il se peut 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 cependant 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 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.
   


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


3. Le mieux pour bien comprendre cette démarche étant de la faire sur un exemple, nous vous conseillons d'essayer de résoudre l'exemple des billes ci-dessus. Vous devriez trouver $y_1 = 1$, $x_1 = 15$, $y_2 = 1$, $x_2 = 10$, $y_3 = 1$, $x_3=6$ et donc $x = 27$. À noter que cette solution est unique modulo $30$ : il se peut que je possède $57$ billes !

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 su se ranger. Le problème peut donc se voir par exemple de la sorte :

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 :

Le butin des pirates

Un autre exemple type, bien que plus anecdotique, est le suivant (merci Wikipédia pour l'énoncé).