Comment résoudre une congruence $ax \equiv b \pmod{n}$ ?

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

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

Exemple corrigé

Difficulté croissante de 1 à 4

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.