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 ! Retrouvez la solution dans cet article 😉