#include<stdio.h>

FILE*f=fopen("inversmodular.in","r");
FILE*g=fopen("inversmodular.out","w");

void gcd ( int a , int b , long long &x , long long &y ){
	
	if ( b == 0 ){
		x = 1; y = 0;
		return ;
	}
	
	long long x0,y0;
	gcd(b,a%b,x0,y0);
	
	x = y0;
	y = x0 - 1LL*(a/b)*y0;
}

int main () {
	
	int A,N;
	fscanf(f,"%d %d",&A,&N);
	
	long long x,y;
	gcd(A,N,x,y);
	
	if ( x < 0 ){
		x = N + (x%N);
	}
	
	fprintf(g,"%lld\n",x);
	
	fclose(f);
	fclose(g);
	
	return 0;
}