#include<stdio.h>

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

int A,N;

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

int main () {
	
	fscanf(f,"%d %d",&A,&N);
	
	int inv,y = 0;
	gcd(A,N,inv,y);
	
	if ( inv <= 0 ){
		int imp = (-inv) / N + 1;
		inv = inv + imp*N;
	}
	
	fprintf(g,"%d\n",inv);
	
	fclose(f);
	fclose(g);
	
	return 0;
}