'''
转换为同余方程求解，用先用欧几里得算法求特解
这个题目a b 必然互质，求出来的特解x % b 就是最小的特解
'''

# 求a, b最大公约数，同时求出裴蜀定理中的一组系数x, y， 满足x*a + y*b = gcd(a, b)
def exp_gcd(a, b):
    flag = True
    if a > b:
        flag = False
        a, b = b, a

    if a == 0:
        return (b, 0, 1) if flag else (b, 1, 0)

    gcd_val, x, y = exp_gcd(b%a, a)
    new_x = y - x * (b // a)
    new_y = x
    return (gcd_val, new_x, new_y) if flag else (gcd_val, new_y, new_x)

a, b = map(int, input().split())
gcd_val, x, y = exp_gcd(a, b)


if x % b == 0:
    x = b
else:
    x = x % b
print(x)