#include <cstdio>
using namespace std;

#define ll long long

void gcd(int a, int b, ll &x, ll &y)
{
    if(!b)
        x = 1, y = 0;
    else
    {
        gcd(b, a % b, x, y);
        ll aux = x;

        x = y;
        y = aux - (a/b) * x;
    }
}

int main()
{

    int a, n;
    ll d, inv = 0, y;

    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    scanf("%d%d", &a, &n);
    gcd(a, n, inv, y);

    if(inv <= 0)
        inv = n + inv % n;

    printf("%lld", inv);

    return 0;
}