En utilisant directement l'inverse de $a$ modulo $n$ lorsque $\mathrm{pgcd}(a,n) = 1$ : $x \equiv a^{-1}b \pmod{n}$

Résoudre $ax \equiv b \pmod{n}$ lorsque $\mathrm{pgcd}(a, n) = 1$ .

L'objectif

Résoudre $ax \equiv b \pmod{n}$ lorsque $\mathrm{pgcd}(a, n) = 1$ .

Le principe

Quand $a$ est inversible modulo $n$ , on multiplie les deux membres par $a^{-1}$ pour obtenir directement $x \equiv a^{-1}b \pmod{n}$ , solution unique modulo $n$ .

La méthode

1
Vérifier que $\mathrm{pgcd}(a, n) = 1$ (sinon utiliser la méthode générale M6).
Comment calculer le PGCD de deux entiers ?Voir
2
Trouver $a^{-1} \pmod{n}$ (par Bézout ou par le petit théorème de Fermat si $n$ est premier).
Comment trouver l'inverse d'un entier $a$ modulo $n$ ?Voir
3
Calculer $x \equiv a^{-1} \cdot b \pmod{n}$ : c'est l'unique solution modulo $n$ .

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Résoudre $3x \equiv 7 \pmod{11}$

Étape 1 —

Vérifier que

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

(sinon utiliser la méthode générale M6).

$\mathrm{pgcd}(3, 11) = 1$ , donc $3$ est inversible modulo $11$ .

Étape 2 —

Trouver

a^{-1} \pmod{n}

(par Bézout ou par le petit théorème de Fermat si

n

est premier).

Bézout : $4 \times 3 - 11 = 1$ , donc $3^{-1} \equiv 4 \pmod{11}$ .

Étape 3 —

Calculer

x \equiv a^{-1} \cdot b \pmod{n}

: c'est l'unique solution modulo

n

$x \equiv 4 \times 7 = 28 \equiv 6 \pmod{11}$ .

Application guidée

Résoudre $5x \equiv 3 \pmod{13}$

Application autonome 1

Résoudre $7x \equiv 2 \pmod{17}$

Application autonome 2

Résoudre $9x \equiv 6 \pmod{19}$

Application autonome 3

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

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

En utilisant directement l'inverse de aaa modulo nnn lorsque pgcd(a,n)=1\mathrm{pgcd}(a,n) = 1pgcd(a,n)=1 : x≡a−1b(modn)x \equiv a^{-1}b \pmod{n}x≡a−1b(modn)

Pour comprendre, fais des exercices !

En utilisant directement l'inverse de $a$ modulo $n$ lorsque $\mathrm{pgcd}(a,n) = 1$ : $x \equiv a^{-1}b \pmod{n}$