#!/usr/bin/env python3

import sys

sys.stdout = open('inversmodular.out', 'w')

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

with open('inversmodular.in', 'r') as fin:
    a, n = tuple(map(int, fin.readline().split()))
    x, _, d = gcd(a, n)
    x = x % n
    while x < 0:
        x += n
    print(x)