#include <cstdio>

#define ll long 

ll a, n;

void euclid(ll a, ll b, ll *x, ll *y)
{
    if (b == 0)
    {
	*x = 1;
	*y = 0;

	return ;
    } 
    ll x0, y0;
    euclid(b, a % b, &x0, &y0);

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

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

    scanf("%ld %ld", &a, &n);

    ll x, y;
    euclid(a, n, &x, &y);
    printf("%ld\n", x);

    return 0;
}