Prépa, 1re année › Arithmétique dans $\mathbb{Z}$ › Résoudre $ax + by = c$ dans $\mathbb{Z}^2$
Résoudre $ax + by = c$ dans $\mathbb{Z}^2$ : méthode (MPSI)
Méthode
Résoudre $ax + by = c$ dans $\mathbb{Z}^2$
Soient $a, b$ non nuls.
- Calculer $d = a \wedge b$. Si $d \nmid c$, il n'y a aucune solution, car $d$ divise $ax + by$ pour tous $x, y$.
- Sinon, diviser par $d$ : $a'x + b'y = c'$ avec $a' \wedge b' = 1$.
- Trouver une solution particulière $(x_0, y_0)$, à vue ou par Euclide étendu (une relation $a'u + b'v = 1$ multipliée par $c'$).
- Soustraire : $a'(x - x_0) = b'(y_0 - y)$. Par Gauss, $b' \mid x - x_0$, donc $x = x_0 + kb'$, puis $y = y_0 - ka'$.
- Vérifier que ces couples conviennent pour tout $k \in \mathbb{Z}$ (réciproque), puis conclure.
Exemple
Équation $21x + 15y = 9$
On a $21 \wedge 15 = 3$ et $3 \mid 9$. L'équation équivaut à $7x + 5y = 3$, avec $7 \wedge 5 = 1$.
Solution particulière : $7 \times (-1) + 5 \times 2 = 3$, donc $(x_0, y_0) = (-1, 2)$.
Si $(x, y)$ est solution, $7(x + 1) = 5(2 - y)$. Donc $5 \mid 7(x+1)$ et $5 \wedge 7 = 1$, d'où $5 \mid x + 1$ par Gauss : $x = -1 + 5k$ avec $k \in \mathbb{Z}$. Alors $5(2 - y) = 35k$, soit $y = 2 - 7k$.
Réciproquement, $7(-1 + 5k) + 5(2 - 7k) = -7 + 10 = 3$.
Ensemble des solutions : $\{(-1 + 5k,\ 2 - 7k),\ k \in \mathbb{Z}\}$.
En revanche, $21x + 15y = 10$ n'a aucune solution, car $3 \nmid 10$.
S’entraîner
- Divisions euclidiennes avec un dividende négatif
- PGCD, coefficients de Bézout et PPCM de 4199 et 1729
- Expressions premières entre elles
- Restes de puissances et divisibilité par congruences
- PGCD dépendant d'un paramètre
Dans le cours
Arithmétique dans $\mathbb{Z}$ : Résoudre $ax + by = c$ dans $\mathbb{Z}^2$