Saurez-vous résoudre des équations diophantiennes ?

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

TakiVeille

TakiVeille