#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long x,y;
int a,n;
void euclext (long long &x, long long &y, int a, int b) 
{ 
	long long aux;
if (b==0) 
{
  x = 1;
  y = 0;
}  
else 
{            
euclext(x,y,b,a%b);
aux=x;
x=y;
y=aux-y*(a/b);
}
}
int main ()
{
	f>>a>>n;
	euclext(x,y,a,n);
	if (x<=0)
		x=n+x%n;
g<<x<<'\n';
return 0;
}