#include<fstream>
#define ll long long
using namespace std;
ll a,b,x,y;

ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");

void gcd_extended(ll a, ll b, ll&x, ll&y){
 if(!b)
   x=1, y=0;
 else{
   ll x0, y0;
   gcd_extended(b, a%b, x0, y0);
   x=y0;
   y=x0-(a/b)*y0;
 }
}

int main(){
cin>>a>>b;
gcd_extended(a,b,x,y);
while(x<0)
  x+=b;
cout<<x;
  return 0;
}