#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

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

int main()
{int a,n,d,x,y;
fin>>a>>n;
Euclid(a,n,d,x,y);
if(x<0) x=x+n;
fout<<x<<"\n";
    return 0;
}