Cette semaine, c'est Alex qui vous propose un #KataOfTheWeek : Équation diophantienne linéaire
Briefing du Kata : Parfois les mathématiques me manquent, alors je vous ai préparé un kata avec un peu d'Algèbre. Ça vous dit ?
Le but de ce kata est de résoudre une équation diophantienne linéaire, en donnant (si elle existe) une de ses solutions.
Trouver une solution (x, y) entiers relatifs pour (a, b, c) entiers relatifs donnés à : ax + by = c
La manière la plus élégante de résoudre ce problème est d'utiliser l'algorithme d'Euclide.
Pour ceux qui ont envie de poser les maths sur papier, vous pouvez démarrer ici. Pour les autres, je vous ai préparé une petite aide.
NB : ces équations possèdent aucunes ou une infinité de solutions calculables à partir d'une solution (x0, y0).
Aide pour résoudre une équation diophantienne linéaire
Voici le process utilisant l'algorithme d'Euclide de manière récursive pour résoudre une équation diophantienne :
ax + by = c (1)
Cette équation a des solutions si et seulement si pgcd(a, b) divise c, si b divise a on a la solution :
x = 0, y = c/b
Si b ne divise pas a, on peut écrire a = bq + r puis substituer dans (1) :
(bq + r)x + by = c
Réarranger:
b(qx + y) + rx = c
On définit:
u = qx + y
v = x
Puis on substitue à nouveau pour obtenir :
bu + rv = c (2)
L'équation (1) a été réduite à (2) avec de plus petits coefficients. Si l'on peut résoudre cette nouvelle équation, on peut retrouver une solution de la précédente avec :
x = v, y = u − qv
Exemple 1 :
25x + 5y = 7
pgcd(a, b) = 5
5 ne divise pas 7, il n'y a pas de solutions.
Exemple 2 :
20x + 11y = 3
pgcd(20, 11) = 1
1 divise 3, il y'a une infinité de solutions?
Utilisons l'algorithme d'Euclide :
20 = 1 x 11 + 9
11 = 1 x 9 + 2
9 = 4 x 2 + 1
2 = 2 x 1 + 0
Et on l'inverse :
1 = 9 - 4 x 2
1 = 9 - 4 x (11 - 1 x 9) = 5 x 9 - 4 x 11
1 = 5 x (20 - 1 x 11) - 4 x 11 = 5 x 20 - 9 x 11
(x, y) = 3 x (5 - 9) = (15, -27) est une solution
Saurez-vous résoudre le problème ?
Bon courage !
Et voici une solution proposée par l'auteur en Java :
public class EuclideUtils {
public static long GCD(long r, long s) {
if (r == 0) return s;
if (s == 0) return r;
if (r < 0) r = -r;
if (s < 0) s = -s;
if (r > s) return GCD(r%s,s);
else return GCD(r,s%r);
}
public static Pair<Long, Long> manualEuclide(long a, long b, long c) {
if (c == 0) {// (0, 0) is a solution
return new ImmutablePair<>(0L,0L);
} else if (a == 0) {
if (b == 0 || c%b != 0) throw new ArithmeticException
("No solution to the linear Diophantine equation " + a + "x + " + b + "y = " + c);
else return new ImmutablePair<>(0L, c/b);//(0, c/b) is a solution
} else if (b == 0) {
if (c%a != 0) throw new ArithmeticException
("No solution to the linear Diophantine equation " + a + "x + " + b + "y = " + c);
else return new ImmutablePair<>(c/a, 0L);//(c/a, 0) is a solution
} else if (c%GCD(a,b) != 0) {//GCD(a, b) does not divide c
throw new ArithmeticException
("No solution to the linear Diophantine equation " + a + "x + " + b + "y = " + c);
}
//a = q*b + r
long q = a/b;
long r = a%b;
if (r == 0) return new ImmutablePair<>(0L, c/b);
else {
Pair sol = manualEuclide(b, r, c);
long u = (long) sol.getLeft();
long v = (long) sol.getRight();
return new ImmutablePair<>(v, u - q * v);
}
}
}Votre équipe TakiVeille
