#include <fstream>
#define ll unsigned long long
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
ll x,y,a,n;
void gcd(ll &x,ll &y,ll a,ll b){
if(b==0) {x=1;y=0;}
else{gcd(x,y,b,a%b);
    ll aux=x;
    x=y;
    y=aux-y*(a/b);
}

}
int main()
{
   f>>a>>n;
gcd(x,y,a,n);
if(x<0) x=x+x%n;
g<<x;
    return 0;
}