Résoudre ax + by = c dans les entiers

Une équation diophantienne est une équation dont on ne cherche que les solutions entières. La plus simple, ax + by = c, se résout entièrement grâce à Bézout.

Quand y a-t-il des solutions ?

L'équation a x + b y = c admet des solutions entières si et seulement si PGCD(a , b) divise c.

La condition est nécessaire : PGCD(a,b) divise ax et by, donc leur somme c. Elle est suffisante grâce à Bézout — il suffit de multiplier l'identité par le bon facteur.

6x + 9y = 21     PGCD(6,9) = 3,  et 3 | 21     ->  il y a des solutions
6x + 9y = 20     3 ne divise pas 20            ->  AUCUNE solution

La seconde ligne se lit aussi directement : 6x + 9y est toujours un multiple de 3, donc ne peut jamais valoir 20.

La méthode complète

1. calculer d = PGCD(a , b) et vérifier que d divise c
2. simplifier l'équation par d
3. trouver UNE solution particulière (Bézout ou à vue)
4. écrire TOUTES les solutions

Sur un exemple :

12 x + 18 y = 30

1. PGCD(12,18) = 6,  et 6 | 30      ->  il y a des solutions
2. on divise par 6 :   2 x + 3 y = 5
3. solution évidente :  x = 1, y = 1   (2 + 3 = 5)     ✔

Toutes les solutions

Une fois l'équation réduite à a'x + b'y = c' avec a' et b' premiers entre eux, et (x0 ; y0) une solution particulière :

x = x0 + b' k
y = y0 - a' k              pour tout entier k

Sur l'exemple  2x + 3y = 5,  avec (x0 ; y0) = (1 ; 1) :

   x = 1 + 3k
   y = 1 - 2k

   k = 0  ->  (1 ; 1)      2 + 3 = 5    ✔
   k = 1  ->  (4 ; -1)     8 - 3 = 5    ✔
   k = -1 ->  (-2 ; 3)    -4 + 9 = 5    ✔

Il y a donc une infinité de solutions, régulièrement espacées.

Pourquoi cette forme ? Si (x ; y) et (x0 ; y0) sont deux solutions, leur différence vérifie a'(x - x0) = -b'(y - y0). Comme a' et b' sont premiers entre eux, le théorème de Gauss impose que b' divise x - x0 — d'où l'écriture x = x0 + b'k. Tout le chapitre se recolle ici.

Un problème concret

Un distributeur ne rend la monnaie qu'en pièces de 2 € et de 5 €. Comment rendre exactement 31 € ?

2x + 5y = 31       PGCD(2,5) = 1 divise 31   ->  possible

solution particulière : y = 1, x = 13   (26 + 5 = 31)

solutions générales :   x = 13 + 5k
                        y = 1 - 2k

Mais un nombre de pièces doit être positif ou nul :

x ≥ 0  ->  13 + 5k ≥ 0  ->  k ≥ -2,6  ->  k ≥ -2
y ≥ 0  ->   1 - 2k ≥ 0  ->  k ≤ 0,5   ->  k ≤ 0

k ∈ {-2 ; -1 ; 0}   ->   (3 ; 5)   (8 ; 3)   (13 ; 1)

Trois solutions concrètes : 3 pièces de 2 € et 5 de 5 €, ou 8 et 3, ou 13 et 1. Cette dernière étape — restreindre aux solutions admissibles — est ce qui distingue un exercice d'un vrai problème.

Où l'on retrouve ces équations

Cryptographie     : inverse modulaire, clés RSA
Calendriers       : synchroniser des cycles de longueurs différentes
Codes correcteurs : théorème des restes chinois
Découpe, monnaie  : problèmes de rendu, optimisation de coupes
Musique           : gammes et tempéraments (rapports de fréquences)

En résumé

• ax + by = c a des solutions entières ssi PGCD(a , b) divise c.
• Méthode : vérifier, simplifier par le PGCD, trouver une solution, généraliser.
• Solutions générales : x = x0 + b'k, y = y0 - a'k avec a', b' premiers entre eux.
• Cette forme se démontre par le théorème de Gauss.
• Un problème concret impose souvent des contraintes de positivité qui réduisent à un nombre fini de solutions.