#include <stdio.h>
#define INPUT "inversmodular.in"
#define OUTPUT "inversmodular.out"


void euclid_extins(int a, int n, int &x, int &y)
{
	if(n == 0)
	{
		x = 1,  y = 0;
		return;
	}
	int x0, y0;
	euclid_extins(n, a%n, x0, y0);
	x = y0;
	y = x0 - (long long)a/n*y0;
}

int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	int a, n;
	scanf("%d %d", &a, &n);
	
	int x, y;
	euclid_extins(a, n, x, y);
	if(x < 0) x = x%n + n;
	printf("%d\n", x);
	
	return 0;
}