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

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

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

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

Exercice d'exemple

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

1

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

2

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

3

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

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) ?

Pour comprendre, passons aux exercices.

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