#include<stdio.h>
int a,n;
void euler(long long &x,long long &y,int a,int b)
{
	if(!b)
	{
		x=1;
		y=0;
		return;
	}
	euler(x,y,b,a%b);
	long long aux=x;
	x=y;
	y=aux-a/b*y;
}
int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d%d",&a,&n);
	long long rez,aux;
	euler(rez,aux,a,n);
	if(rez<=0)
		rez=n+rez%n;
	printf("%lld\n",rez);
	return 0;
}