def gcd_step(a, b):
    """
    Performs a single step of the gcd algorithm.
    Example: gcd_step(1071, 462) == (2, 147) because 1071 == 2 * 462 + 147.
    """
    if a < b:
        return (0, b)

    res = 0
    while a >= b:
        a -= b
        res += 1
    return (res, a)