Equations Diophantiennes.

On considère trois entiers relatifs a, b et c non nuls.
Les équations diophantiennes sont de la forme ax + by = c où les inconnues sont les entiers relatifs x et y.
Ces équations ont des solutions si et seulement si c est un multiple du PGCD de a et de b.

En effet, si d désigne le PGCD de a et de b, d divise toutes combinaisons linéaires de a et de b.
Par conséquent d divise ax + by et donc d doit diviser c. Autrement dit, c doit être un multiple de d.
Réciproquement, si c est un multiple de d = PGCD (a ; b) alors il existe c' tel que c = c'×d.
De plus, il existe également a' et b' tels que a = a'×d et b = b'×d avec a' et b' premiers entre eux.
Par conséquent, d'après le théorème de Bézout, il existe u et v tels que a'u + b'v = 1.
D'où, en multipliant par c = dc' (≠ 0) on arrive a : dc'×a'u + dc'×b'v = dc'×1. soit a×c'u + b×c'v = c.
L'équation admet au moins une solution, le couple (c'u ; c'v).

Exemple 1 : Justifier si les équations suivantes admettent des solutions dans ℤ².

15x - 26y = 5	42x + 26y = 5
15 = 3×5 et 26 = 2×13 donc PGCD(15 ; 26) = 1 5 est bien un multiple de 1 L'équation admet des solutions.	42 = 6×7 = 2×3×7 et 26 = 2×13 donc PGCD(42 ; 26) = 2 5 n'est pas un multiple de 2 L'équation n'admet de solution dans ℤ2.

Remarque : Pour résoudre l'équation 15x - 26y = 5 sans utiliser la méthode décrite ci-après, on considère la fonction f(x) = (15x-5)/26.
On cherche des couples consécutifs d'entiers relatifs dans un tableau de valeurs. On trouve pour x ∈ [0 ; 50] : (9 ; 5) et (35 ; 20).
On suppose que le second couple s'obtient à partir du premier pour k = 1. On note x₀ = 9, y₀ = 5, et x₁ = 35, y₁ = 20.
La différence des x est 35 - 9 = 26 et celle des y est 20 - 5 = 15. On a donc x₁ = 1×26 + x₀ et y₁ = 1×15 + y₀.
En remplaçant 1× par k×, on arrive à des solutions générales de la forme (26k + 9 ; 15k +5) avec k ∈ ℤ..

En utilisant la méthode décrite ci-après, PGCD(26 ; 15) = 1. on cherche u et v tel que 15u - 26v = 1.
On a 26×4 = 104, 15×7 = 105 et 15×7 - 26×4 = 1. D'où 15×35 - 26×20 = 5 en multipliant par 5.
Une solution particulière est telle que x₀ = 35 et y₀ = 20. De plus ici a' = a = 15 et b' = b = -26
Finalement, on arrive à (-26k + 35 ; -15k + 20) avec k ∈ ℤ.
Cette expression n'est pas identique à celle obtenue par l'autre méthode, mais elles sont équivalentes...
Pour k = 0 et k = 1 retrouve bien respectivement les deux couples (35 ; 20) et (9 ; 5).
Un changement de variable permet de passer de lune à l'autre expression.
Par exemple, on change k par (1 - k) dans la première expression :
(26k + 9 ; 15k +5) → (26(1 - k) + 9 ; 15(1 - k) +5) = (-26k + 35 ; -15k + 20)

Résoudre une équation diophantienne : ax + by = c

On cherche le PGCD des nombres a et b. On vérifie que c est un multiple de ce PGCD.

Si NON (c n'est pas un multiple du PGCD) alors l'équation n'a pas de solutions dans ℤ².

Si OUI (c est un multiple du PGCD) alors l'équation admet des solutions dans ℤ².

• On divise l'équation par le PGCD.
  En posant d = PGCD(a ; b), a = a'×d, b = b'×d et c = c'×d.
  On obtient ainsi une équation "simplifiée" a'x + b'y = c' où a' et b' sont premiers entre eux.

• On cherche une solution particulière (x₀ ; y₀) à cette équation.
  Si on n'y arrive pas on cherche d'abord une solution particulière à l'équation a'x + b'y = 1.
  En multipliant par c', on obtient un couple (x₀ ; y₀) tel que a'x₀ + b'y₀ = c'.

• On a alors d'une part a'x + b'y = c' et d'autre part a'x₀ + b'y₀ = c'.
  Donc a'x + b'y = a'x₀ + b'y₀ soit encore a'x - a'x₀ = b'y₀ - b'y
  c'est-à dire a'(x - x₀) = b'(-y + y₀)
  Cela signifie que a'(x - x₀) est divisible par b' ou que b' divise a'(x - x₀)
  Or a' et b' sont premiers entre eux donc d'après le théorème de Gauss, b' divise (x - x₀).
  Par conséquent, il existe un entier relatif k tel que (x - x₀) = b'×k.
  D'où l'expression x = x₀ + b'×k

• On reporte cette expression dans la dernière équation on obtient :
  a'(x₀ + b'×k - x₀) = b'(-y +y₀) soit a'×b'×k = b'(-y +y₀) c'est-à dire a'×k = (-y +y₀)
  D'où l'expression y = y₀ - a'×k .

• On vérification que les couples trouvés sont bien solutions de l'équation initiale.
  

  a(x0 + b'k) + b(y0 - a'k) =	ax0 + ab'k + by0 - ba'k
  =	d×a'x0 + d×a'b'k + d×b'y0 - d×b'a'k
  =	d×(a'x0+ b'y0) = d×c' = c

  Car d = PGCD(a ; b), a = d×a', b = d×b' et c = d×c'.

• Les solutions de l'équation ax + by = c sont les couples de la forme :
  (x₀ + b'k ; y₀ - a'k) avec k ∈ ℤ.

Remarques :Si on considère a et b strictement positifs.
L'équation ax - by = c admettra pour solutions des couples du type (x₀ - b'k ; y₀ - a'k) avec k ∈ ℤ.
Pour l'équation -ax + by = c les solutions seront du type (x₀ + b'k ; y₀ + a'k) avec k ∈ ℤ.