#include <cstdio>
using namespace std;
int a, n;
int euclid(int a, int b, int &x, int &y){
    if(b==0){
        x = 1; y = 0; return a;
    }
    else{
        int tmp, d;
        d = euclid(b, a%b, x, y);
        //x = y0, y = x0 - y0(a/b);
        tmp = y;
        y = x - y*(a/b);
        x = tmp;
        return d;
    }
}
int main()
{
    int 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=x+n;
    printf("%d\n", x);
    return 0;
}