#include <stdio.h>

int a,n;

void ext(long long &x,long long &y,int a,int b)
{
	if(!b)
		x=1,y=0;
	else
	{
		ext(x,y,b,a%b);
		long long fuck = x;
		x=y;
		y=fuck-y*(a/b);
	}
}

int main()
{
	long long inv=0,y;

	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);

	scanf("%d %d",&a,&n);
	ext(inv,y,a,n);

	if(inv<=0)
		inv=n+inv%n;

	printf("%lld",inv);
	return 0;
}