#include <fstream>
#include <iostream>

using namespace std;

long long a,n,x,y;

void solve( long long n , long long a )
{
	if (a==0)
	{
		x=1;y=0;
		return ;
	}
	
	solve (a,n%a);
	long long  aux=y;
	y=x-(n/a)*y;
	x=aux;
}

void afisare ()
{
	FILE *f=fopen ("inversmodular.out","w");
	while (y<0) y+=n;
	fprintf (f,"%lld",y);
	fclose(f);
}

void citire ()
{
	FILE *f=fopen ("inversmodular.in","r");
	fscanf (f,"%lld%lld",&a,&n);
	fclose(f);
}

int main ()
{
	citire ();
	solve(n,a);
	afisare();
	return 0;
}