#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 = x+n;
    printf("%d", x);
    return 0;
}
int euclid(int a, int b, int &x, int &y){
    int aux, d;
    if(b==0){
        x = 1; y = 0;
        return a;
    }
    d = euclid(b, a%b, x, y);
    aux = x;
    x = y;
    y = aux - y*(a/b);
    return d;
}