#include <cstdio>
long long inv , ins;
int a, m;

void euclid (long long &x, long long &y, int a, int b)
{
     if (b==0)
     {
         x = 1;
         y = 0;
     }
     else
     {
         long long d;
         euclid(x, y, b, a % b);
         d= x;
         x = y;
         y = d - y * (a / b);
     }
}

int main()
{


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

    scanf("%d %d", &a, &m);
    euclid(inv, ins, a, m);

    printf("%d\n", inv);

    return 0;
}