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

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éfinition
On dit que le nombre $y$ est l'inverse de $x$ modulo $n$ si $x\cdot y \equiv 1 \pmod 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 :

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

3. Théorème des restes chinois

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.

Problème
Je possède un sachet de billes. Si je les dispose en tas de...
  • $2$ billes, il en reste une toute seule,
  • $3$ billes, il n'en reste pas,
  • $5$ billes, il en reste deux.
Combien ai-je de billes ?

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.

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$ sont des nombres entiers, 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.$$

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.

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 à nouveau d'une simple équation linéaire, et la solution est donnée par
    $$y_1 \equiv (n_2\cdot n_3 \cdot \ldots \cdot n_k)^{-1} \pmod {n_1}.$$ On trouve par la même occasion $x_1$.
    De la même façon, on peut pour chaque $i \in \left\{1, \dots, k\right\}$ trouver un $x_i$ qui soit solution du système avec des zéros partout et un $1$ dans la $i$-ème ligne.
    Ce n'est alors plus qu'une formalité de vérifier que $x = a_1 \cdot x_1 + \dots + a_k \cdot x_k$ est solution du 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

  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 !

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

Problème
Lorsque les militaires se placent en rangs de $5$, il en reste $2$ qui n'ont pas su se ranger. En rangs de $7$, il en reste $3$, En rangs de $8$, il en reste $6$, en rangs de $9$, il en reste un seul, en rangs de $11$, il n'en reste pas, et en rangs de $13$, il en reste $8$. Sachant que l'armée de Han Xin comporte moins de $300.000$ soldats, combien sont-ils exactement ?

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 :

Problème
Nous sommes un $30$ janvier, et une pleine lune est prévue après-demain. Quand verrons-nous une pleine lune le jour du nouvel an ?

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

Problème
Une bande de 17 pirates possède un trésor constitué de pièces d'or d'égale valeur. Ils projettent de se les partager également, et de donner le reste au cuisinier chinois. Celui-ci recevrait alors 3 pièces. Mais les pirates se querellent, et six d'entre eux sont tués. Un nouveau partage donnerait au cuisinier 4 pièces. Dans un naufrage ultérieur, seuls le trésor, six pirates et le cuisinier sont sauvés, et le partage donnerait alors 5 pièces d'or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisinier s'il décide d'empoisonner le reste des pirates ?

Solution
Si $x$ désigne cette fois-ci 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..