#include <fstream>
using namespace std;
void euclid(int a,int b,int &x,int &y)
{
  if(!b)
  {
    x=1; y=0;
    return;
  }
  int x0=0,y0=0;
  euclid(b,a%b,x0,y0);
  x=y0;
  y=x0-y0*(a/b);
}
int main()
{
    int a,n,x=0,y=0;
    ifstream fi("inversmodular.in");
    ofstream fo("inversmodular.out");
    fi>>a>>n;
    euclid(a,n,x,y);
    while(x<=0) x+=n;
    fo<<x<<"\n";
    return 0;
}