#include <cstdio>
using namespace std;
long long a,n;
//verifica ecuatia a * x + b * y = d unde d este cmmdc(a,b)
void euclidextins(long long a, long long b, long long &d, long long &x, long long &y)
{
if (b == 0)
{
x = 1;
y = 0;
d = a;
}
else
{
long long x0, y0;
euclidextins(b,a % b,d,x0,y0);
x = y0;
y = x0 - (a / b) * y0;
}
}
void citire()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%lld%lld",&a,&n);
}
int main()
{
long long d,x,y;
citire();
euclidextins(a,n,d,x,y);
while (x < 0)
x += n;
printf("%lld\n",x);
return 0;
}