📐

Équations diophantiennes : résolution et méthodes

Nov 16, 2024

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.