#include <stdio.h>
long long A,N;

void gcd(long long &cx,long long &cy,long long x,long long y){
	if (y==0){
		cx=1;
		cy=0;
		return ;
	}
	gcd(cx,cy,y,x%y);
	int cp=cx;
	cx=cy;
	cy=cp-cy*(x/y);
}

int main(){

	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);

	scanf("%lld%lld",&A,&N);

	fclose(stdin);

	long long cx,cy;

	gcd(cx,cy,A,N);

	if (cx<0) cx=(cx%N)+N;

	printf("%lld\n",cx);

	fclose(stdout);

	return 0;
}