from typing import Tuple


def extended_gcd(a: int, b: int) -> Tuple[int, int, int]:
    """
        Recursive extended euclidean algorithm to find the greatest common denominator and its linear combination
        Returns g, m, n such that gcd(a, b) = g = m*a + n*b
        
        Parameters
        ----------
        
        a
            Number to find the greatest common denominator of with b
        b
            Number to find the greatest common denominator of with a
    """
    if a == 0:
        # Trivial case
        return (b, 0, 1)
    else:
        # Call self with a and b % a since this is equivalent as per euclidean algorithm
        g, m, n = extended_gcd(b % a, a)
        # Return gcd, n, and m
        return (g, n - (b // a)*m, m)