#include <iostream>
#include <algorithm>
#define FIN "inversmodular.in"
#define FOUT "inversmodular.out"
#define int long long
using namespace std;
int A,N;

inline int GCD(int A,int B,int &X,int &Y){

	if (B==0){

		X=1;
		Y=0;
		return A;
	} else {

		int X0,Y0;
		int D=GCD(B,A%B,X0,Y0);
		X=Y0;
		Y=X0-(A/B)*Y0;
		return D;
	}
}


void iofile(void){

	freopen(FIN,"rt",stdin);
	freopen(FOUT,"wt",stdout);

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

	fclose(stdin);

}

void solve(void){

	int X,Y;
	int div=GCD(A,N,X,Y);
	if (X<0){ int AX=abs(X); X+=N*(AX/N+1);} else {X%=N;}

	printf("%lld\n",X);
	fclose(stdout);
}

#undef int

int main(void){

	iofile();
	solve();
	return 0;
}