#include<cstdio>
#define infile "inversmodular.in"
#define outfile "inversmodular.out" 
using namespace std;

typedef long long ll;

void citeste();
void rezolva();
void afiseaza();

int N,A;
int X;

void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d",&A,&N);
	
	fclose(stdin);
}


int euclid(int a, int b, int&x, int &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	
	int d,x0,y0;
	
	d = euclid(b,a%b,x0,y0);
	
	x = y0;
	
	y = x0 - (a/b) * y0;
	
	return d;
}




void rezolva()
{
	int d,y;
	
	d = euclid(A,N,X,y);
	
	while(X<=0)
		X = N + X%N;
}




void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%d\n",X);
	
	fclose(stdout);
}


int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}