#include<stdio.h>

#define i64 long long

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

int A,N;

void gcd ( i64 &x, i64 &y , int A, int B ){
	
	if ( !B ){
		x = 1; y = 0;
		return ;
	}
	
	i64 x0,y0;
	gcd ( x0 , y0 , B , A % B );
	x = y0;
	y = x0 - (A / B) * y0;
}

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