Résolution des équations diophantiennes du type AX + BY = C

Introduction

• Objectif : Résoudre les équations de la forme AX + BY = C où A, B, C sont des entiers et les inconnues X et Y aussi.

Critère d'existence de solutions

• L'équation a des solutions (entiers) si et seulement si le PGCD de A et B divise C.

Calcul des solutions

1. Existence de solutions

   • Si le PGCD de A et B divise C, il existe des solutions.
   • Exemple : Pour l'équation 161X + 368Y = 115, calcul du PGCD de 161 et 368 :
     • 368 = 161 * 2 + 46
     • 161 = 46 * 3 + 23
     • 46 = 23 * 2
     • PGCD = 23
   • 115 = 5 * 23, donc le PGCD divise C.

2. Trouver une solution particulière

   • Utilisation des coefficients de Bézout.
   • Remontée de l'algorithme d'Euclide pour exprimer 23 :
     • 23 = 161 + 46 * (-3)
     • Substituer 46 par 368 - 2 * 161 et simplifier.
     • 161 * 7 + 368 * (-3) = 23
     • Multiplier par 5 pour obtenir : 161 * 35 + 368 * (-15) = 115
   • Solution particulière : (x0, y0) = (35, -15)

3. Déduire toutes les solutions

   • Forme générale des solutions :
     • x = x0 + αk
     • y = y0 + βk
   • Pour notre exemple :
     • 161x + 368y = 115
     • Utiliser la solution particulière : 161x0 + 368y0 = 115
     • 161(x - x0) + 368(y - y0) = 0
     • En divisant par 23, obtenir : 7(x - x0) = -16(y - y0)
     • Implique que 7 divise 16(y - y0), donc 7 divise (y - y0)
     • y - y0 = 7k, x - x0 = -16k
   • Solutions générales :
     • x = 35 - 16k
     • y = -15 + 7k
   • k est un entier parcourant Z et est le même pour x et y.