//MS
#include <cstdio>
long long s1 , s2;
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 - (a / b) * y;
        // y = d - y * (a / b);
     }
}

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


    scanf("%d %d", &a, &m);
    euclid(s1, s2, a, m);

    if (s1 <= 0)
       s1 = m + s1 % m;

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

    return 0;
}