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

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

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

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.

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)

Exemple corrigé

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