#include <cstdio>
using namespace std;
void euclid_extins(int a,int b,int &d,int &x,int &y)
{

if(b==0)
    {
    d=a;
    x=1;
    y=0;
    }
else {
     int x1,y1;
     euclid_extins(b,a%b,d,x1,y1);
     x=y1;
     y=x1-y1*(a/b);
     }
}
inline int abs(int x)
{
if(x<0)return -x; else return x; return 0;
}
int main()
{ int a,n;
freopen("inversmodular.in","r",stdin); scanf("%d %d",&a,&n); fclose(stdin);
int d=0,x=0,y=0;
euclid_extins(a,n,d,x,y);
if(x<0)x=x+(abs(x)/n+1)*n;
freopen("inversmodular.out","w",stdout); printf("%d",x); fclose(stdout);
return 0;
}