#include<fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
void A(int a,int b,int &d,int &x,int &y)
{
    if(b) {
        A(b,a%b,d,x,y);
        int z=x;
        x=y,y=z-a/b*y;
    } else
        d=a,x=1,y=0;
}
int main()
{
    int a,b,d=0,x=0,y=0;
    return cin>>a>>b,A(a,b,d,x,y),cout<<(x<0?b+x%b:x),0;
}