def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def factorization(number):
    prime_numbers = []
    divisor = 2
    while divisor ** 2 < number:
        if number % divisor == 0:
            count = 1
            while number % divisor == 0:
                count += 1
            prime_numbers.append([divisor, count])
        divisor += 1
    if number > 1:
        prime_numbers.append([number, 1])

    return prime_numbers


def modulo_pow(number, degree, modulo):
    if degree == 0:
        return 1
    elif degree % 2:
        return modulo_pow(number, degree - 1, modulo) * number % modulo
    return modulo_pow(number * number % modulo, degree // 2, modulo) % modulo


def inverse_num(m, a):
    if gcd(m, a) != 1:
        return -1
    phi = 1
    for prime in factorization(m):
        phi *= ((prime[0] ** prime[1]) - (prime[0] ** (prime[1] - 1)))
    return modulo_pow(a, phi - 1, m)


m, a = map(int, input().split())
print(inverse_num(m, a))