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

Que ferais-tu face à un exercice de ce type ?

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

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, passons aux exercices.

Exercice d'exemple

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

1

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

2

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

3

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

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.

Comment résoudre une congruence ax≡b(modn)ax \equiv b \pmod{n}ax≡b(modn) ?

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, passons aux exercices.

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