def _extended_euclidean(q, r):
    """Return a tuple (p, a, b) such that p = aq + br,
    where p is the greatest common divisor.
    """

    # see [Davenport], Appendix, p. 214

    if abs(q) < abs(r):
        p, a, b = _extended_euclidean(r, q)
        return p, b, a

    Q = 1, 0  # noqa: N806
    R = 0, 1  # noqa: N806

    while r:
        quot, t = divmod(q, r)
        T = Q[0] - quot*R[0], Q[1] - quot*R[1]  # noqa: N806
        q, r = r, t
        Q, R = R, T     # noqa: N806

    return q, Q[0], Q[1]