Étape 1
Pour que le système admette au moins une solution, il est nécessaire et suffisant que les solutions de la première congruence vérifient également la seconde congruence.
Étape 2
Commençons par résoudre dans $\mathbb{Z}$ la congruence $17x \equiv 4 \pmod{29}$. Le nombre 29 est premier et ne divise pas 17, donc $\text{PGCD}(17, 29) = 1$. D'après le théorème de Bézout, 17 admet un inverse modulo 29.
Étape 3
Appliquons l'algorithme d'Euclide pour obtenir une relation de Bézout entre 17 et 29 : $$29 = 1 \times 17 + 12$$ $$17 = 1 \times 12 + 5$$ $$12 = 2 \times 5 + 2$$ $$5 = 2 \times 2 + 1$$ En remontant les égalités : $$1 = 5 - 2 \times 2$$ $$1 = 5 - 2 \times (12 - 2 \times 5) = 5 \times 5 - 2 \times 12$$ $$1 = 5 \times (17 - 12) - 2 \times 12 = 5 \times 17 - 7 \times 12$$ $$1 = 5 \times 17 - 7 \times (29 - 17) = 12 \times 17 - 7 \times 29$$
Étape 4
On en déduit l'égalité $12 \times 17 - 7 \times 29 = 1$, ce qui donne $12 \times 17 \equiv 1 \pmod{29}$. Ainsi, 12 est un inverse de 17 modulo 29.
Étape 5
En multipliant les deux membres de la congruence $17x \equiv 4 \pmod{29}$ par 12, on obtient : $$12 \times 17x \equiv 12 \times 4 \pmod{29}$$ ce qui équivaut à : $$x \equiv 48 \pmod{29}$$ Comme $48 = 1 \times 29 + 19$, l'ensemble des solutions de la première équation est constitué des entiers $x$ tels que $x \equiv 19 \pmod{29}$.
Étape 6
Pour que le système admette une solution, la seconde congruence $5x \equiv k \pmod{29}$ doit être vérifiée pour ces entiers. On remplace $x$ par 19 : $$k \equiv 5 \times 19 \pmod{29}$$ Or $5 \times 19 = 95$. La division euclidienne de 95 par 29 donne : $$95 = 3 \times 29 + 8$$ On en déduit que $k \equiv 8 \pmod{29}$.
Étape 7
Comme la condition imposée est $0 \le k \le 28$, la seule valeur possible est $k = 8$.
Méthode clé
Pour résoudre $ax \equiv b \pmod n$ lorsque $\text{PGCD}(a, n) = 1$, on utilise l'algorithme d'Euclide pour déterminer une relation de Bézout $au + nv = 1$, ce qui fournit un inverse $u$ de $a$ modulo $n$.
Piège à éviter
Ne pas oublier que l'existence d'un inverse modulaire requiert que le coefficient et le modulo soient premiers entre eux, et veiller à réduire correctement modulo 29 à chaque étape.
