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