- Calculer $323 \wedge 391$.
- Montrer que l'équation $323x + 391y = 100$ n'a aucune solution dans $\mathbb{Z}^2$.
- Résoudre dans $\mathbb{Z}^2$ l'équation $(E) : 323x + 391y = 85$.
- L'équation $(E)$ admet-elle des solutions dans $\mathbb{N}^2$ ?
Appliquer l'algorithme d'Euclide à $391$ et $323$.
Le PGCD divise toute expression $323x + 391y$.
Diviser $(E)$ par le PGCD, puis chercher une solution particulière de l'équation réduite par Euclide étendu.
Après soustraction de la solution particulière, appliquer le lemme de Gauss. Ne pas oublier la réciproque.
Pour la question 4, comparer la taille des coefficients et du second membre.
1. Algorithme d'Euclide : $$391 = 1 \times 323 + 68, \quad 323 = 4 \times 68 + 51, \quad 68 = 1 \times 51 + 17, \quad 51 = 3 \times 17 + 0.$$ Donc $323 \wedge 391 = 17$. On a d'ailleurs $323 = 17 \times 19$ et $391 = 17 \times 23$.
2. Pour tous $x, y \in \mathbb{Z}$, $17$ divise $323x + 391y$. Comme $100 = 5 \times 17 + 15$, $17 \nmid 100$ : l'équation n'a aucune solution.
3. On a $85 = 5 \times 17$, donc $(E)$ équivaut à $19x + 23y = 5$, avec $19 \wedge 23 = 1$.
Solution particulière. Euclide sur $23$ et $19$ : $23 = 1 \times 19 + 4$, $19 = 4 \times 4 + 3$, $4 = 1 \times 3 + 1$. En remontant : $$1 = 4 - 3 = 4 - (19 - 4 \times 4) = 5 \times 4 - 19 = 5(23 - 19) - 19 = 5 \times 23 - 6 \times 19.$$ En multipliant par $5$ : $19 \times (-30) + 23 \times 25 = 5$. Le couple $(-30, 25)$ est solution.
Analyse. Si $(x, y)$ est solution, alors $19x + 23y = 19 \times (-30) + 23 \times 25$, d'où $19(x + 30) = 23(25 - y)$. Ainsi $23 \mid 19(x+30)$ et $23 \wedge 19 = 1$, donc $23 \mid x + 30$ par le lemme de Gauss : $x = -30 + 23k$ avec $k \in \mathbb{Z}$. Alors $19 \times 23k = 23(25 - y)$, soit $y = 25 - 19k$.
Synthèse. Pour tout $k \in \mathbb{Z}$, $19(-30 + 23k) + 23(25 - 19k) = -570 + 575 = 5$.
En posant $k = j + 1$, on obtient une écriture plus simple : l'ensemble des solutions de $(E)$ est $$\{(-7 + 23j,\ 6 - 19j),\ j \in \mathbb{Z}\}.$$ Vérification pour $j = 0$ : $323 \times (-7) + 391 \times 6 = -2261 + 2346 = 85$.
4. Une solution vérifie $x \geqslant 0$ si et seulement si $23j \geqslant 7$, soit $j \geqslant 1$, et $y \geqslant 0$ si et seulement si $19j \leqslant 6$, soit $j \leqslant 0$. Ces conditions sont incompatibles : $(E)$ n'a aucune solution dans $\mathbb{N}^2$. On le voit aussi directement : si $y \geqslant 1$, $323x + 391y \geqslant 391 > 85$ ; si $y = 0$, $323x = 85$ est impossible.
$323\wedge391=17$ ; aucune solution pour $100$ ; $\{(-7+23j,\ 6-19j),\ j\in\mathbb{Z}\}$ ; aucune solution dans $\mathbb{N}^2$