#include <stdio.h>

int a, n;


void euclid (int a, int b, int &d, int &x, int &y)
{
	if (b == 0) 
	{
		d=a;
		x=1;
		y=0;
		return;
	}
	int x1, y1;
	euclid (b, a%b, d, x1, y1);
	x=y1;
	y=x1-y1*(a/b); //parte intreaga din a/b
}

int main ()
{
	freopen ("inversmodular.in", "r", stdin);
	freopen ("inversmodular.out", "w", stdout);
	scanf ("%d%d", &a, &n);
	int d, x, y;
	euclid (a, n, d, x, y);
	x=x%n;
       	while (x < 0)
		x += n;
	printf ("%d\n", x);	
	return 0;
}