Algoritmo Euclideo


import numpy
from decimal import *
from random import *

getcontext().prec = 800

# Algoritmo A


def Euclidean(u, v):
    print("(", u, ",", v, ")")
    if v > u:
        return Euclidean(v, u)
    while v != 0:
        r = u % v
        u = v
        v = r
        print("=(", u, ",", v, ")")
    return u


# Algoritmo X
def XEuclidean(u, v, verbose=False):
    # extended euclidean algorithm
    U = numpy.array([1, 0, int(u)])
    V = numpy.array([0, 1, int(v)])
    if verbose:
        print("U=", U, "")
        print("V=", V, "\n")
    while V[2] != 0:
        q = U[2] // V[2]
        R = U - V * q
        # print "R=",R,"\n"
        U = V
        V = R
        if verbose:
            print("U=", U, "")
            print("V=", V, "\n")
            print(
                u,
                "*",
                U[0],
                "+",
                v,
                "*",
                U[1],
                "=",
                U[2],
                "\n",
            )
    # (u0,u1,u2) -> u*u0+v*u1=u2
    return U