#include<stdio.h>

void euclid (long long a, long long b, long long &x, long long &y)
{
	if ( b == 0 )
	{
		x = 1;
		y = 0;
	}
	else
	{
		long long x0, y0;
		euclid (b, a%b, x0, y0);
		x = y0;
		y = x0 - (a/b)*y0;
	}
}

int main ()
{
	long long x, y;
	int a, n;
	
	FILE *fis = fopen ("inversmodular.in", "r");
	fscanf(fis, "%d %d", &a, &n);
	fclose(fis);
	
	euclid (a, n, x, y);
	if ( x <= 0 )
		x = n + x%n;
	
	FILE *fis2 = fopen ("inversmodular.out", "w");
	fprintf(fis2, "%I64d\n", x);
	fclose(fis2);
	
	return 0;
}