#include <stdio.h>

int gcd(int a,int b)
{
	int r;
	while (b!=0)
	{
		r = a%b;
		a = b;
		b = r;
	}
	return a;
}

void egcd(int a, int b, int* x1, int* x2)
{
	if (a==0)
	{
		*x1 = 0;
		*x2 = 1;
		return;
	}

	int _x1, _x2;
	egcd(b%a, a, &_x1, &_x2);
	
	*x1 = _x2 - (b/a) * _x1;
	*x2 = _x1;
}

int main()
{
	int a,n;

	FILE *fin = fopen("inversmodular.in","rb");
	FILE *fout = fopen("inversmodular.out","wb");

	fscanf(fin,"%d %d",&a, &n);
	int x1, x2;
	egcd(a,n,&x1,&x2);
	while (x1<0)
	{
		x1 += n;
	}
	fprintf(fout,"%d\n",x1);


	return 0;
}