Une équation diophantienne linéaire demande des nombres entiers, pas seulement des réels. Comparons la théorie à 18x + 12y = 72, de l’algorithme d’Euclide à toutes les solutions. Nous ne cherchons pas un couple chanceux par essais : nous construisons une procédure complète, puis imposons les contraintes éventuelles du problème.
Ouvrir le laboratoire : saisir a, b et c et suivre toutes les étapes
1. Équation de départ
| Partie théorique | Exemple pratique |
|---|---|
La forme est ax + by = c, avec a, b, c ∈ ℤ. Nous cherchons x, y ∈ ℤ. | 18x + 12y = 72 |
Pour la procédure principale, supposons a, b ≠ 0. Les coefficients nuls sont traités à la fin. | a = 18, b = 12, c = 72 |
2. Calcul du plus grand commun diviseur
Appliquons l’algorithme d’Euclide : chaque division produit un reste inférieur au diviseur.
| Partie théorique | Exemple pratique |
|---|---|
Calculons d = PGCD(|a|,|b|) par divisions successives. | 18 = 12×1 + 6 |
| Divisons le diviseur précédent par le reste, jusqu’à obtenir un reste nul. | 12 = 6×2 + 0 |
| Le dernier reste non nul est le PGCD, pris positif. | d = 6 |
3. Vérification de l’existence des solutions
| Partie théorique | Exemple pratique |
|---|---|
Des solutions entières existent si et seulement si d ∣ c : le PGCD divise le second membre. | 6 ∣ 72 |
Si le PGCD ne divise pas c, aucun couple entier n’existe. Sinon, poursuivons. | 72/6 = 12 |
Pourquoi est-ce nécessaire ? Tout ax + by est multiple du PGCD. Pourquoi est-ce suffisant ? L’identité de Bézout, construite ensuite, produit une solution dès que c/d est entier.
4. Euclide étendu et identité de Bézout
Remonter les divisions signifie réécrire les restes comme combinaisons des coefficients initiaux.
| Partie théorique | Exemple pratique |
|---|---|
| Isolons le dernier reste non nul et remplaçons les restes précédents à rebours si nécessaire. | 6 = 18 - 12 |
Nous obtenons deux entiers u, v tels que au + bv = d : c’est l’identité de Bézout. | 18(1) + 12(-1) = 6 |
Les coefficients de cette combinaison sont u et v. | u = 1, v = -1 |
5. Calcul d’une solution particulière
Transformons l’identité de Bézout en l’équation initiale en multipliant partout par le même nombre.
| Partie théorique | Exemple pratique |
|---|---|
Partons de au + bv = d. | 18(1) + 12(-1) = 6 |
Le multiplicateur est m = c/d. | 72/6 = 12 |
Multiplions toute l’identité : a(um) + b(vm) = c. | 18(12) + 12(-12) = 72 |
Ainsi x₀ = u(c/d) et y₀ = v(c/d). | x₀ = 12, y₀ = -12 |
Le couple (12,-12) est correct même si une coordonnée est négative : pour l’instant, nous cherchons dans ℤ. La non-négativité est une exigence supplémentaire.
6. Démonstration de la formule générale
| Partie théorique | Exemple pratique |
|---|---|
| Écrivons l’équation initiale. | 18x + 12y = 72 |
| Écrivons l’équation satisfaite par la solution particulière. | 18(12) + 12(-12) = 72 |
| Soustrayons membre à membre. | 18(x - 12) + 12(y + 12) = 0 |
| Passons le deuxième terme à droite. | 18(x - 12) = -12(y + 12) |
Divisons les deux membres par d. | 3(x - 12) = -2(y + 12) |
Posons a′ = a/d et b′ = b/d. Ces nombres sont premiers entre eux. De a′(x - x₀) = -b′(y - y₀), le lemme d’Euclide donne b′ ∣ (x - x₀).
Il existe donc un entier k tel que x - x₀ = b′k. En remplaçant et simplifiant, nous obtenons y - y₀ = -a′k.
x = x₀ + (b/d)ky = y₀ - (a/d)kk ∈ ℤ
Nous avons prouvé que toute solution a cette forme. Réciproquement, en remplaçant dans l’équation, les termes en k s’annulent : tout entier k donne une solution. Aucune ne manque.
7. Application de la formule générale
| Partie théorique | Exemple pratique |
|---|---|
Première coordonnée : x = x₀ + (b/d)k. | x = 12 + (12/6)k |
Deuxième coordonnée : y = y₀ - (a/d)k. | y = -12 - (18/6)k |
Simplifions en rappelant que k peut être n’importe quel entier. | x = 12 + 2k; y = -12 - 3k; k ∈ ℤ |
Les formules décrivent une infinité de solutions entières, y compris avec des coordonnées négatives. Une autre solution particulière peut donner des formules d’apparence différente, mais elles représentent la même famille après un décalage du paramètre.
8. Recherche des solutions non négatives
Si le problème exige des quantités non négatives, imposons les deux conditions, pas une seule.
| Partie théorique | Exemple pratique |
|---|---|
Imposons x₀ + (b/d)k ≥ 0. | 12 + 2k ≥ 0 ⇒ k ≥ -6 |
Imposons y₀ - (a/d)k ≥ 0. | -12 - 3k ≥ 0 ⇒ k ≤ -4 |
Prenons l’intersection des intervalles et seulement les valeurs entières de k. | -6 ≤ k ≤ -4 |
Une contrainte générale s’écrit q + tk ≥ m, avec m = 0 pour des quantités non négatives et m = 1 pour des quantités entières strictement positives.
- Si
t > 0:k ≥ ⌈(m - q)/t⌉. - Si
t < 0:k ≤ ⌊(m - q)/t⌋; diviser par un nombre négatif inverse l’inégalité. - Si
t = 0, vérifions directementq ≥ m.
⌈ ⌉ et ⌊ ⌋ désignent respectivement l’arrondi supérieur et inférieur. Un intervalle vide signifie qu’aucune solution n’est admissible ; avec des coefficients de signes opposés, l’intervalle peut être non borné.
9. Calcul des solutions
Dans l’exemple k ∈ {-6,-5,-4}. Remplaçons chaque valeur dans les deux formules.
| k | x = 12 + 2k | y = -12 - 3k |
|---|---|---|
| -6 | 0 | 6 |
| -5 | 2 | 3 |
| -4 | 4 | 0 |
Les trois solutions non négatives sont (0,6), (2,3), (4,0). Vérification : 18×0 + 12×6 = 72, 18×2 + 12×3 = 72, 18×4 + 12×0 = 72.
Si nous demandons x ≥ 1 et y ≥ 1, il ne reste que (2,3). « Entières », « non négatives » et « strictement positives » sont trois demandes différentes.
10. Résumé de la méthode
| Étape | Partie théorique | Exemple pratique |
|---|---|---|
| Équation | ax + by = c | 18x + 12y = 72 |
| PGCD | d = PGCD(|a|,|b|) | d = 6 |
| Existence | d ∣ c | 6 ∣ 72 |
| Bézout | au + bv = d | 18 - 12 = 6 |
| Multiplicateur | m = c/d | m = 12 |
| Solution particulière | x₀ = um, y₀ = vm | (12,-12) |
| Formule générale : x | x = x₀ + (b/d)k | x = 12 + 2k |
| Formule générale : y | y = y₀ - (a/d)k | y = -12 - 3k |
| Contraintes | x, y ≥ 0 | -6 ≤ k ≤ -4 |
| Solutions | k ∈ ℤ | (0,6), (2,3), (4,0) |
11. Deux tâches distinctes, même avec de grands nombres
- Euclide étendu trouve une solution particulière sans tâtonnement.
- La formule générale produit toutes les autres solutions en faisant varier l’entier
k.
Pour 252x + 198y = 900, les divisions sont 252 = 198×1 + 54, 198 = 54×3 + 36, 54 = 36×1 + 18, 36 = 18×2 + 0. Le PGCD est 18.
En remontant, nous obtenons 18 = 4×252 - 5×198. Multiplions par 900/18 = 50 : une solution particulière est (200,-250). La famille est x = 200 + 11k, y = -250 - 14k.
La non-négativité impose k ≥ -18 et k ≤ -18. Donc k = -18 et le seul couple non négatif est (2,2). Chargez cet exemple dans le laboratoire pour voir chaque substitution à rebours.
12. Impossibilités, signes et coefficients nuls
Aucune solution entière : 18x + 12y = 73 est impossible car 6 ne divise pas 73. Aucune solution non négative : 6x + 10y = 2 a pour famille x = 2 + 5k, y = -1 - 3k, mais exige simultanément k ≥ 0 et k ≤ -1.
Coefficients négatifs : appliquons Euclide aux valeurs absolues. Si |a|u′ + |b|v′ = d, il suffit de rétablir les signes dans les coefficients de Bézout pour obtenir au + bv = d. La formule générale et les contraintes restent valables.
- Si
a = 0etb ≠ 0, il faut quebdivisec:y = c/best fixé etxest libre. - Si
b = 0eta ≠ 0, de mêmex = c/aest fixé etyest libre. - Si
a = b = 0etc ≠ 0, aucune solution. Sic = 0aussi, tout couple entier convient :x = s,y = t, avec deux paramètres indépendants.
Le laboratoire utilise une arithmétique entière exacte, sans arrondir les coefficients. Il accepte jusqu’à 80 chiffres pour chacun des trois paramètres et distingue les formules complètes du tableau, qui affiche au plus 25 solutions par page.
Ouvrir le laboratoire : saisir a, b et c et suivre toutes les étapes