#include <cstdio>

using namespace std;

int a, m;
int d;

void citire()
{
    scanf("%d %d", &a, &m);
}

void euclidExtins(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        d = a;
    }
    else
    {
        euclidExtins(b, a % b, x, y);

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

void solve()
{
    int x, y;

    euclidExtins(a, m, x, y);

    while(x < 0)
    {
        x += m;
    }

    printf("%d\n", x);
}

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

    citire();
    solve();

    return 0;
}