#include <stdio.h>
#define LL long long

int A,N;

void euclid_extins(LL& x,LL& y, int A,int B){
	if( B == 0 ){
		x=1; y=0;
		return;
	}
	euclid_extins(x,y,B,A%B);
	int aux=x;
	x=y;
	y=aux-y*(A/B);
}

int main(){
	LL x=0,y=0;
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d%d",&A,&N);
	
	euclid_extins(x,y,A,N);
	
	while( x<=0 ) x=N+x%N;
	
	printf("%lld\n",x);
	fclose(stdin); fclose(stdout);
	return 0;
}