def pgcd(a,b):
    if b==0:
        return a
    else:
        while a!=b:
            if a>=b:
                a -= b
            else:
                b -= a
    return a