#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout ("inversmodular.out");


void euclid (int a, int b, int *x, int *y)
{
    if (b==0)
    {
        *x=1;
        *y=0;
        return;
    }
    else
    {
        int x0,y0;
        euclid (b,a%b,&x0,&y0);
        *x=y0;
        *y=x0-(a/b)*y0;
    }
}

int main ()
{
    int X,N,x,y;
    fin>>X>>N;
    euclid (X,N,&x,&y);
    while (x<0) x=x+N;
    while (x>=N) x=x-N;
    fout<<x;
}