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

void euclid(int &x,int &y,int a,int b){
    if(!b)
    {
        x=1;
        y=0;
        return ;
    }
    euclid(x,y,b,a%b);
    int newx=y;
    int newy=x-y*(a/b);
    x=newx;
    y=newy;
}

int main()
{
    int x,y,a,b;
    in>>a>>b;
    euclid(x,y,a,b);
    x %=b;
    if(x<0)
        x+=b;
    out<<x;
    return 0;
}