Logo maths-cours.fr maths-cours.fr
Logo maths-cours.fr maths-cours.fr
Connexion Inscription
Divisibilité et congruences Méthode

Résoudre une congruence linéaire ax = b [n]

Durée estimée
15 minutes
Votre progression

Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.

Créer un compte

Situation

On cherche à déterminer tous les entiers relatifs $x$ vérifiant une congruence linéaire de la forme

$ ax \equiv b \ \left[n\right] $

où $a$, $b$ sont des entiers relatifs et $n$ un entier naturel non nul.

Une telle congruence n'a pas toujours de solution, et lorsqu'elle en a, ses solutions forment une ou plusieurs classes de congruence modulo $n$. Le PGCD de $a$ et $n$ joue ici un rôle central.

Méthode

  1. Étape 1 — Tester l'existence des solutions. Calculer $d = \text{PGCD}(a, n)$. La congruence $ax \equiv b \ \left[n\right]$ admet des solutions si et seulement si $d$ divise $b$. Si $d$ ne divise pas $b$, conclure immédiatement : il n'y a aucune solution.
  2. Étape 2 — Se ramener au cas où $a$ et $n$ sont premiers entre eux. Si $d = 1$, passer directement à l'étape 3. Sinon, diviser les trois nombres par $d$ : la congruence $ax \equiv b \ \left[n\right]$ équivaut à $a'x \equiv b' \ \left[n'\right]$ avec $a' = \dfrac{a}{d}$, $b' = \dfrac{b}{d}$ et $n' = \dfrac{n}{d}$. Par construction, $a'$ et $n'$ sont premiers entre eux.
  3. Étape 3 — Déterminer un inverse de $a'$ modulo $n'$. Comme $\text{PGCD}(a', n') = 1$, le théorème de Bézout fournit deux entiers $u$ et $v$ tels que $a'u + n'v = 1$. On les obtient par l'algorithme d'Euclide étendu. On a alors $a'u \equiv 1 \ \left[n'\right]$ : l'entier $u$ est un inverse de $a'$ modulo $n'$.
  4. Étape 4 — Isoler $x$. Multiplier les deux membres de $a'x \equiv b' \ \left[n'\right]$ par $u$ : on obtient $x \equiv ub' \ \left[n'\right]$. Réduire $ub'$ modulo $n'$ pour obtenir un représentant $x_0$ avec $0 \leqslant x_0 < n'$.
  5. Étape 5 — Décrire l'ensemble des solutions. Les solutions sont tous les entiers $x \equiv x_0 \ \left[n'\right]$. Si $d = 1$, cela donne une unique classe modulo $n$. Si $d > 1$, cette unique classe modulo $n'$ se traduit par $d$ classes distinctes modulo $n$ : $x_0,\ x_0 + n',\ x_0 + 2n',\ \dots,\ x_0 + (d-1)n'$.

Cas où $a$ et $n$ sont premiers entre eux : $3x \equiv 5 \pmod 7$

  1. Étape 1 : $\text{PGCD}(3, 7) = 1$, et $1$ divise $5$. La congruence admet donc des solutions, formant une unique classe modulo $7$.
  2. Étape 2 : Comme le PGCD vaut déjà $1$, $3$ et $7$ sont premiers entre eux : rien à simplifier.
  3. Étape 3 : On cherche un inverse de $3$ modulo $7$ par l'algorithme d'Euclide étendu. La division euclidienne donne $7 = 2 \times 3 + 1$, d'où $1 = 7 - 2 \times 3$. Ainsi $-2 \times 3 \equiv 1 \ \left[7\right]$ : un inverse de $3$ modulo $7$ est $-2$, soit $5$ puisque $-2 \equiv 5 \ \left[7\right]$.

  4. Étape 4 : On multiplie la congruence par cet inverse :

    $ 5 \times 3x \equiv 5 \times 5 \ \left[7\right] $

    Or $5 \times 3 = 15 \equiv 1 \ \left[7\right]$, donc le membre de gauche se réduit à $x$. À droite, $5 \times 5 = 25 \equiv 4 \ \left[7\right]$. On obtient $x \equiv 4 \ \left[7\right]$.

  5. Étape 5 : L'ensemble des solutions est l'ensemble des entiers congrus à $4$ modulo $7$.

Vérification : $3 \times 4 = 12 = 7 + 5 \equiv 5 \ \left[7\right]$, ce qui confirme le résultat.

L'ensemble des solutions est $x \equiv$ $\mathbf{4 \ \left[7\right]}$.

Cas où $\text{PGCD}(a, n) > 1$ : $4x \equiv 6 \pmod{10}$

  1. Étape 1 : $\text{PGCD}(4, 10) = 2$, et $2$ divise $6$. La congruence admet donc des solutions ; comme $d = 2$, on s'attend à deux classes de solutions modulo $10$.

  2. Étape 2 : On divise les trois nombres par $d = 2$. La congruence $4x \equiv 6 \ \left[10\right]$ équivaut à

    $ 2x \equiv 3 \ \left[5\right] $

    où $2$ et $5$ sont désormais premiers entre eux.

  3. Étape 3 : On cherche un inverse de $2$ modulo $5$. La division euclidienne donne $5 = 2 \times 2 + 1$, d'où $1 = 5 - 2 \times 2$. Ainsi $-2 \times 2 \equiv 1 \ \left[5\right]$ : un inverse de $2$ modulo $5$ est $-2 \equiv 3 \ \left[5\right]$, car $2 \times 3 = 6 \equiv 1 \ \left[5\right]$.

  4. Étape 4 : On multiplie $2x \equiv 3 \ \left[5\right]$ par cet inverse $3$ :

    $ 3 \times 2x \equiv 3 \times 3 \ \left[5\right] $

    Le membre de gauche se réduit à $x$ car $3 \times 2 = 6 \equiv 1 \ \left[5\right]$. À droite, $3 \times 3 = 9 \equiv 4 \ \left[5\right]$. On obtient $x \equiv 4 \ \left[5\right]$.

  5. Étape 5 : La solution $x \equiv 4 \ \left[5\right]$ correspond, modulo $10$, aux deux classes $x \equiv 4 \ \left[10\right]$ et $x \equiv 4 + 5 \equiv 9 \ \left[10\right]$.

Vérification : $4 \times 4 = 16 \equiv 6 \ \left[10\right]$ et $4 \times 9 = 36 \equiv 6 \ \left[10\right]$, ce qui confirme les deux classes.

L'ensemble des solutions est $x \equiv 4 \ \left[10\right]$ ou $x \equiv$ $\mathbf{9 \ \left[10\right]}$.

Remarque

Pour un petit module $n$, on peut aussi déterminer un inverse de $a$ par tâtonnement, en testant les produits $a \times 1$, $a \times 2$, $\dots$ jusqu'à tomber sur un résultat congru à $1$ modulo $n$. L'algorithme d'Euclide étendu reste cependant indispensable dès que le module devient grand, où le tâtonnement n'est plus praticable.

Attention

La condition d'existence est essentielle : avant tout calcul, vérifier que $\text{PGCD}(a, n)$ divise $b$. Par exemple, $4x \equiv 3 \ \left[10\right]$ n'a aucune solution, car $\text{PGCD}(4, 10) = 2$ ne divise pas $3$ (le membre de gauche $4x$ est toujours pair, donc jamais congru à un nombre impair modulo $10$).

Ne pas oublier non plus, dans le cas $d > 1$, de remonter à toutes les classes modulo $n$ : une fois la solution trouvée modulo $n' = \dfrac{n}{d}$, elle se décline en $d$ classes distinctes modulo $n$. Se contenter de l'unique classe modulo $n'$ revient à perdre une partie des solutions.