Équation diophantienne ax+by = c - Définition

Introduction

L'équation ax + by = c, où les coefficients a, b, et c, sont trois entiers relatifs et où les inconnues x et y sont entiers relatifs, est une des équations diophantiennes les plus simples à résoudre. Sa résolution s'appuie sur l'algorithme d'Euclide, le théorème de Bachet-Bézout et le théorème de Gauss. Lorsque c est égal au PGCD de a et b, on parle parfois d’identité de Bézout.

Dans l'ensemble des entiers relatifs, une telle équation possède, ou bien aucune solution, ou bien une infinité de solutions. Lorsque les coefficients et les inconnues sont des entiers naturels, l'équation possède un nombre fini de solutions. Le théorème de Paoli en donne le nombre à 1 près.

Recherche de solutions dans l'ensemble des entiers relatifs

Équation ax + by = 1 où a et b sont premiers entre eux

Le théorème de Bachet-Bézout affirme que cette équation admet toujours au moins une solution.

La première étape de la résolution consiste à trouver une solution particulière , c'est-à-dire un couple d'entiers relatifs (x₀, y₀) vérifiant : ax₀ + by₀ = 1.

• L'algorithme d'Euclide étendu permet d'en exhiber une.
• Une autre méthode consiste à utiliser le développement en fraction continue de a/b, l'avant dernière réduite fournit une solution du problème: Si est l'avant dernière réduite de alors k_{n − 1}a − h_{n − 1}b = ( − 1)^{n + 1}.
• Mais on peut aussi, si b n'est pas trop grand, chercher une solution par simple balayage en travaillant modulo b et en cherchant un entier x₀ compris entre 1 et |b| - 1, vérifiant , l'entier y₀ se calcule alors comme étant égal à .

En effet, il est facile de vérifier qu'un tel couple est solution du problème :

Il s'agit maintenant de prouver que seuls ces couples sont solutions. Supposons donc que le couple (x ,y) est solution de l'équation. On a donc

En regoupant autrement les termes, on obtient

L'entier b divise donc le produit a(x - x₀). Comme a et b sont premiers entre eux, le lemme de Gauss permet de dire que b divise x - x₀. Il existe donc un entier relatif k tel que x - x₀ = kb. Soit encore

En remplaçant x - x₀ par kb dans (2) on obtient :

Puis en simplifiant par -b

Soit encore

Donc, si (x,y) est solution de (1) alors, il existe un entier relatif k tel que (x,y) = (x₀+bk, y₀ - ak)

Équation ax + by = c où a et b sont premiers entre eux

Une solution particulière peut être trouvée en multipliant par c une solution particulière de l'équation ax + by = 1. En effet, si (x₀, y₀) vérifie ax₀ + by₀ = 1 alors ax₀c + by₀c = c, le couple (x₀c, y₀c) est alors solution de l'équation ax + by = c.

Un raisonnement analogue au précédent permet de trouver l'ensemble des solutions :

Cas général

On appelle d le pgcd de a et de b.

En effet, d divisant a et b, d divise aussi toute expression de la forme ax + by où a et b sont des entiers relatifs, donc d doit diviser c

On suppose maintenant que d divise c, il existe alors 3 entiers relatifs a₁, b₁, et c₁ tels que

a = da₁

b = db₁

c = dc₁

avec a₁et b₁ premiers entre eux.

L'équation ax + by = c est alors équivalente à l'équation a₁x + b₁y = c₁ dans laquelle a₁ et b₁ sont premiers entre eux, et ce cas a déjà été résolu. On obtient alors la résolution dans le cas général :

Une solution particulière (x₁, y₁) étant connue, l'ensemble des solutions est formé des couples (x₁+b₁k, y₁ - a₁k) où k est un entier relatif quelconque.

D'où la propriété :

Système minimal

On suppose dans cette section que c est un multiple de d. Parmi toutes les solutions d'une équation ax + by = c donnée, on peut chercher celle(s) pour laquelle x² + y² soit la plus petite possible.

Il s'agit de rendre minimal la valeur (x₁ + b₁k)² + (y₁ − a₁k)². Si on considère la fonction de la variable réelle t définie parf(t) = (x₁ + b₁t)² + (y₁ − a₁t)², l'étude de cette fonction du second degré montre que celle-ci possède un minimum en

Si t est entier, le couple solution est alors (x₁ + b₁t,y₁ − a₁t), sinon, l'entier qui rend f minimal est le (ou les) entier(s) k le(s) plus proche(s) de t.

Le(s) couple(s) d'entiers solution de ax + by = c dont la valeurx² + y² est minimale sont le (ou les) couple(s) (x₁ + b₁k,y₁ − a₁k) où k est le (ou les) entier(s) k le(s) plus proche(s) de .

Dans le cas où a et b sont premier entre eux, le cas où t est entier mérite d'être explicité. On démontre que t est entier si et seulement si l'entier c est un multiple dea² + b². La solution du système minimal est alors .

Dans le cas où a et b sont premiers entre eux, il existe deux solutions au système minimal si et seulement si a et b sont impairs et l'entier c est un multiple impair de