provides extended gcd functionality for finding coprime numbers s and t such that num1 s num2 t gcdnum1 num2 ie the coefficients of bzout s identity extended gcd algorithm return s t g such that num1 s num2 t gcdnum1 num2 and s and t are coprime extended gcd algorithm return s t g such that num1 s num2 t gcd num1 num2 and s and t are co prime
def extended_gcd(num1, num2):
    

    old_s, s = 1, 0
    old_t, t = 0, 1
    old_r, r = num1, num2

    while r != 0:
        quotient = old_r / r

        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    return old_s, old_t, old_r