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