def egcd(a, b):
    """
    see https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

    >>> egcd(18, 24)
    (6, -1, 1)
    >>> egcd(64, 32)
    (32, 0, 1)
    >>> egcd(35, 24)
    (1, 11, -16)
    """
    if b == 0:
        return a, 1, 0
    d, s, t = egcd(b, a % b)
    return d, t, s - (a // b) * t