#include <cstdio>
using namespace std;
int euclid(int a, int b, int &x, int &y);

int main()
{
    int a, n, x, y;
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%d%d", &a, &n);
    euclid(a, n, x, y);
    while(x<0) x += n;
    printf("%d\n", x);
    return 0;
}
int euclid(int a, int b, int &x, int &y)
{
    if(b==0){x=1; y=0;return a;}
    int d, aux;
    d = euclid(b, a%b, x, y);
    aux = y;
    y = x - y*(a/b);
    x = aux;
    return d;
}