#include <stdio.h>
#define i64 long long
using namespace std;

	void EuclidExtins(int a,int b,i64 &x,i64 &y)
	{if(!b)	x=1,y=0;
	 else 
		 {i64 x0,y0;
		  EuclidExtins(b,a%b,x0,y0);
		  x=y0; y=x0-(a/b)*y0;
		 }
	}
	
int main(void)
{FILE *fin=fopen("inversmodular.in","r");
 FILE *fout=fopen("inversmodular.out","w");
 int a,n;
 i64 x,y;
 
 fscanf(fin,"%d%d",&a,&n);
 EuclidExtins(a,n,x,y);
 while(x<=0) x+=n;
 fprintf(fout,"%d",x);
 fclose(fin); fclose(fout);
 return 0;
}