Justins Extended Euclidean Algorithm

justin.py

def qr(x,y):
    q=x//y
    r=x-q*y
    if r<0:
       q+=1
       r-=y
    return q,r

def eea(x, y):
    r0=x
    r1=y
    if (y == 0): # This part is to deal with the zero division error
        r1 = r0
        s1 = 1
        t1 = 0
        r2 = 0
    else:
        s0, s1 = 1, 0
        t0, t1 = 0, 1
        q,r2 = qr(r0,r1)
        s2 = s0 - s1*q
        t2 = t0 - t1*q        
    while r2 > 0:
        r0, r1 = r1, r2
        s0, s1 = s1, s2
        t0, t1 = t1, t2
        q,r2 = qr(r0,r1)
        s2 = s0 - s1*q
        t2 = t0 - t1*q
    gcd = r1
    a=s1
    b=t1
    return f"For x={x} and y={y}. There exist a={a} and b={b} such that ({a})({x})+({b})({y})={gcd}=gcd({x},{y})"