Euclidean Algorithm


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