def pgcd(a, b): #http://python.jpvweb.com/mesrecettespython/doku.php?id=pgcd_ppcm
    """Retourne le pgcd de a et b. Version etendu du pgcd avec le 1er coef
    de bezout (pour inversion modulaire de a).

    >>> pgcd(35, 21)
    7
    >>> pgcd(2016, 1996)
    4
    """
    r, u = a, 1
    rp, up = b, 0
    while rp != 0:
        q = r // rp
        rs, us = r, u
        r, u = rp, up
        rp, up = (rs - q * rp), (us - q * up)
    return r