def euclide_bezout_direct(a, b):
    """
    Renvoie d = pgcd(a, b) et les deux constantes u et v.  L'idee
    est de faire un calcul direct sans passer par la construction
    de la liste E.  On applique les formules (unpeu plus compliquees)
    de bezoutCroissant.

    A la fin de la boucle, le pgcd est la valeur de a.
    """
    u = 1
    v = 0
    x = 0
    y = 1
    while b != 0:
        q = a // b
        r = a % b
        print(a, b, q, r)
        tmp_u = u
        tmp_v = v
        u = x
        v = y
        print(u, v)
        x = tmp_u - q * x
        y = tmp_v - q * y
        a = b
        b = r
    return a, u, v
    

def euclide_bezout(a, b):
    u, v = bezout(euclide(a, b))
    return u*a +b*v, u, v


def euclide(a, b):
    E = []
    while b != 0:
        L = [a, b, a//b, a%b]
        E.append(L)
        a = L[1]
        b = L[3]
    return E


def bezout(E):
    """
    E est la liste des listes produites par l'algorithme d'Euclide
    applique a a et b, ou
    a, b = E[0][0 : 2].

    L'algoritme renvoie les constantes de la formule de Bezout
    calculees en une boucle descendente ; on a besoin d'une relation de
    recurrence d'ordre 1 (mais croisee entre u et v).
    """
    u = 0
    v = 1
    for k in range(len(E) - 2, -1, -1):
        tmp = v
        v = u -E[k][2]*v
        u = tmp
    return u, v


def bezoutCroissant(E):
    """
    E est la liste des listes produites par l'algorithme d'Euclide
    applique a a et b, ou
    a, b = E[0][0 : 2].

    L'algoritme renvoie les constantes de la formule de Bezout
    calculees en une boucle croissante ; on a besoin d'une relation de
    recurrence d'ordre 2 pour chacun des u et v.

    Il y a un probleme si la longueur de E est 1, i.e. si b divise a.
    """
    u = 1
    v = 0
    x = 0
    y = 1
    for k in range(len(E)):
        tmp_u = u
        tmp_v = v
        u = x
        v = y
        print(E[k], "and", u, v)
        x = tmp_u - E[k][2] * x
        y = tmp_v - E[k][2] * y
    return u, v


a = 24
b = 15
E = euclide(a, b)
print(E)

u, v = bezout(E)
print(f"Avec bezout, les constantes pour {a} et {b} sont")
print(f"u = {u}, v = {v}, avec la verification pgcd = {u*a +v*b}")

u, v = bezoutCroissant(E)
print(f"\nAvec bezoutCroissant, les constantes pour {a} et {b} sont")
print(f"u = {u}, v = {v}, avec la verification pgcd = {u*a +v*b}\n\n")

print(euclide_bezout_direct(a, b))