import sys

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

def mulinv(b, n):
    g, x,_= egcd(b, n)
    if g == 1:
        return x%n
    else:
        return -1

n,a=map(int,input().split())
print(mulinv(a,n))