#include <stdio.h>

const char IN[]   ="inversmodular.in";
const char OUT[]  ="inversmodular.out";
typedef long long ll;

int N,A;

void gcd(ll &x,ll &y,int a,int b)
{
	if (!b)
		x=1,y=0;
	else
	{
		gcd(x,y,b,a%b);
		ll aux= x;
		x=y;
		y= aux - y * (a/b);
	}
}

int rez()
{
	ll inv,aux;
	gcd(inv,aux,A,N);
	
	if (inv<=0)
		inv= N + inv % N;
	
	return inv;
}

void scriere(int x)
{
	freopen(OUT,"w",stdout);
	printf("%d\n",x);
	fclose(stdout);
}

void citire()
{
	freopen(IN,"r",stdin);
	scanf("%d%d",&A,&N);
	fclose(stdin);
}

int main()
{
	citire();
	scriere(rez());
	return 0;
}