Équation de Bézout en Python

Résoudre une équation de Bézout en Python n’est pas si difficile que ce que l’on pourrait imaginer au premier abord.

Nous allons dans un premier temps faire un rappel sur la manière dont on résout mathématiquement une telle équation, puis nous allons voir une implémentation en Python.

Équation de Bézout en Python: rappels mathématiques

Équation de Bézout en Python: définition

Une équation de Bézout est une équation à deux variables entières x et y de la forme:$$ax+by=c$$On la trouve aussi sous le nom d’équation diophantienne mais c’est très abusif. En effet, une équation de Bézout est un cas particulier des équations diophantiennes.

Résultat mathématique: existence des solutions

L’équation ax + by = c admet des solutions entières uniquement si c est divisible par pgcd(a ; b).

Ainsi, l’équation ax + by = 1 admet des solutions quand a et b sont premiers entre eux.

Résultat mathématique: valeurs des solutions

Pour trouver les solutions de l’équation ax + by = 1 quand a et b sont premiers entre eux, il faut avant tout trouver une solution particulière.

Pour cela, on utilise l’algorithme d’Euclide. Prenons un exemple: on souhaite résoudre l’équation 17x + 13y = 1. L’algorithme d’Euclide donne:

17 = 1 × 13 + 4
13 = 3 × 4 + 1
4 = 4 × 1 + 0

On “remonte” l’algorithme à partir de “1”:

1 = 13 - 3 × 4
1 = 13 - 3 × (17 - 1 × 13)
1 = 4 × 13 - 3 × 17

Une solution particulière est donc x = -3 et y = 4. On a alors:

17  x  + 13 y  = 1
17(-3) + 13(4) = 1

Donc, en soustrayant la seconde ligne à la première, on a:

17(x+3) + 13(y-4)=0
17(x+3) = 13(4-y)

D’après le théorème de Gauss, comme 13 et 17 sont premiers entre eux, 13 divise x+3. Il existe donc un entier k tel que:$$x+3=13k\quad\text{soit}\quad x=-3+13k.$$En injectant dans l’équation \(17(x+3)=13(4-y)\) cette valeur de x, on obtient:$$17\times13k=13(4-y)$$soit, en divisant par 13:$$17k=4-y$$et donc:$$y=4-17k.$$

Ainsi, toutes les solutions de l’équation sont de la forme:$$(-3+13k;4-17k)\quad,\quad k\in\mathbb{Z}.$$

Équation de Bézout en Python: implémentation

Fonctions principales

Nous allons considérer que les équations à résoudre sont de la forme ax + by = 1, avec pgcd(a ; b) = 1.

def bezout_fct(a,b):
    if b == 0:
        return 1,0
    else:
        u , v = bezout_fct(b , a % b)
        return v , u - (a//b)*v

def resoud_equation(a,b,c):
    u,v = bezout_fct(a,b)
    return "Les solutions de l'équation {}x + {}y = {} sont:\n({} + {}k , {} - {}k)".format(a,b,c,u,b,v,a)

La première fonction retourne les deux valeurs particulières de l’équation.

La seconde retourne l’ensemble des solutions.

>>> resoud_equation(17,13,1)
Les solutions de l'équation 17x + 13y = 1 sont:
(-3 + 13k , 4 - 17k)

Une fonction pgcd un peu spéciale

from math import log

def pgcd(a,b,la=0,lb=0,lq=0,lr=0,olda=0,oldb=0,affiche=False,bezout=False,nombre=False):
    if a < b:
        a,b = b,a
    r = a % b
    
    if affiche == True:
        q = a // b
    
        if la == 0:
            la = str( int( log( a , 10 ) ) + 1 )
            lb = str( int( log( b , 10 ) ) + 1 )
            lq = str( int( log( q , 10 ) ) + 2 )
            lr = str( int( log( r , 10 ) ) + 1 )
    
        s = '{:'+la+'} = {:'+lq+'} × {:'+lb+'} + {:'+lr+'}'
        print(s.format(a,q,b,r))
    
    if r == 0:
        if affiche == True:
            response = '\npgcd({};{}) = {}'.format(olda,oldb,b)
        else:
            if nombre == False:
                response = 'pgcd({};{}) = {}'.format(olda,oldb,b)
            else:
                response = b
        
        if bezout == True:
            u , v = bezout_fct(olda,oldb)
            response += "\n\nUne solution particulière de l'équation {}x + {}y = 1 est : x = {}, y = {}.".format(olda,oldb,u,v)
            
        return response
    else:
        if olda == 0:
            olda, oldb = a, b
        return pgcd(b,r,la,lb,lq,lr,olda,oldb,affiche,bezout,nombre)

Cette fonction est légèrement plus compliquée qu’une simple fonction retournant le PGCD de deux nombres car je voulais qu’elle fasse bien plus à l’origine.

En effet, je voulais que cette fonction puisse afficher l’algorithme d’Euclide. Avec cette fonction, on a:

>>> print( pgcd(155,35,affiche=True) )
155 = 4 × 35 + 15
35 = 2 × 15 + 5
15 = 3 × 5 + 0

pgcd(155;35) = 5

Il n’était pas utile d’avoir une fonction si compliquée pour résoudre une équation de Bézout, mais j’avais envie d’un petit “plus”.

Une application

Si x représente le nombre d’hommes et y celui des femmes, on a l’équation suivante:$$8x+5y=100.$$

Le programme précédent ne donne pas les solutions particulières de cette équation car c est différent de 1. Je dois donc le modifier un peu à l’arrache:

def resoud_equation(a,b,c):
    d = pgcd(a,b,nombre=True)
    if c == 1 and d == 1:
        u,v = bezout_fct(a,b)
        return "Les solutions de l'équation {}x + {}y = {} sont: ({} + {}k , {} - {}k)".format(a,b,c,u,b,v,a)
    elif d == 1:
        y = 0
        while (c - b*y)%a != 0:
            y += 1
        return "Les solutions de l'équation {}x + {}y = {} sont: ({} + {}k , {} - {}k)".format(a,b,c,(c-b*y)//a,b,y,a)
    else:
        return "L'équation {}x + {}y = {} n'a pas de solutions entières.".format(a,b,c)

Je vous l’accorde, c’est bien moche… Mais ça fait le job (en s’en contentera pour le moment). On obtient alors:

>>> resoud_equation(8,5,100)
Les solutions de l'équation 8x + 5y = 100 sont: (10 + 5k , 4 - 8k)

Comme les valeurs de x et y sont strictement positives, il n’y a que deux solutions:

• si k = 0 alors x = 10 et y = 4;
• si k = -1 alors x = 5 et y = 12.

Et voilà ! Notre problème est résolu !