En posant $d = \mathrm{pgcd}(a,n)$ : l'équation admet des solutions ssi $d \mid b$ ; on divise alors par $d$ et on résout $a'x \equiv b' \pmod{n'}$ avec $a'=a/d$ , $b'=b/d$ , $n'=n/d$ , en trouvant l'inverse de $a'$ modulo $n'$ par Bézout

Déterminer toutes les solutions entières de $ax \equiv b \pmod{n}$ .

L'objectif

Déterminer toutes les solutions entières de $ax \equiv b \pmod{n}$ .

Le principe

Une congruence $ax \equiv b \pmod{n}$ est résoluble si et seulement si $\mathrm{pgcd}(a,n) \mid b$ ; en divisant par $d = \mathrm{pgcd}(a,n)$ , on se ramène à un cas où $a'$ est inversible modulo $n'$ .

La méthode

1
Calculer $d = \mathrm{pgcd}(a, n)$ . Si $d \nmid b$ , l'équation n'a pas de solution. Sinon, poser $a' = a/d$ , $b' = b/d$ , $n' = n/d$ .
Comment calculer le PGCD de deux entiers ?Voir
2
Résoudre $a'x \equiv b' \pmod{n'}$ : appliquer Bézout pour trouver $u$ tel que $a'u \equiv 1 \pmod{n'}$ , puis $x_0 = b'u \bmod n'$ .
Comment trouver l'inverse d'un entier $a$ modulo $n$ ?Voir
3
L'ensemble des solutions de l'équation initiale est $\{x_0 + kn' \mid k \in \mathbb{Z}\}$ (exactement $d$ classes modulo $n$ ).

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Résoudre $6x \equiv 4 \pmod{10}$

Étape 1 —

Calculer

d = \mathrm{pgcd}(a, n)

. Si

d \nmid b

, l'équation n'a pas de solution. Sinon, poser

a' = a/d

b' = b/d

n' = n/d

$d = \mathrm{pgcd}(6, 10) = 2$ et $2 \mid 4$ , donc des solutions existent. On pose $a' = 3$ , $b' = 2$ , $n' = 5$ .

Étape 2 —

Résoudre

a'x \equiv b' \pmod{n'}

: appliquer Bézout pour trouver

u

tel que

a'u \equiv 1 \pmod{n'}

, puis

x_0 = b'u \bmod n'

Résoudre $3x \equiv 2 \pmod{5}$ : Bézout donne $3 \times 2 - 5 \times 1 = 1$ , donc $3^{-1} \equiv 2 \pmod{5}$ . Alors $x_0 = 2 \times 2 = 4 \pmod 5$ .

Étape 3 —

L'ensemble des solutions de l'équation initiale est

\{x_0 + kn' \mid k \in \mathbb{Z}\}

(exactement

d

classes modulo

n

Solutions : $x \equiv 4 \pmod{5}$ , soit les deux classes modulo $10$ : $x \equiv 4 \pmod{10}$ ou $x \equiv 9 \pmod{10}$ .

Application guidée

Résoudre $4x \equiv 6 \pmod{10}$

Application autonome 1

Résoudre $4x \equiv 3 \pmod{10}$ (pas de solution)

Application autonome 2

Résoudre $15x \equiv 9 \pmod{21}$

Application autonome 3

Résoudre $9x \equiv 12 \pmod{15}$ .

Crée ton compte gratuit pour accéder à la fiche et aux exercices