#include <cstdio>

#define verf(x, N) \
  if (x <= 0) \
    x = N + x % N

int A, N;

void euclid(int A, int B, int &X, int &Y)
{
     if ( !B )
         X = 1, Y = 0;
     else
     {
         euclid(B, A % B, X, Y);
         int aux = X;
         X = Y;
         Y = aux - Y * (A / B);
     }
}

int main()
{
    int inv = 0, ins;

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

    scanf("%d %d", &A, &N);

    euclid(A, N, inv, ins);

    verf(inv, N);

    printf("%d", inv);

    return 0;
}