#include<cstdio>
using namespace std;
#define	fcl	fclose(stdin);	fclose(stdout);	return 0
	#define	SUBMIT 2333
typedef long long LL;
LL A,B;
void ExGcd(LL a,LL b,LL& x,LL& y){
	if(b==0){
		x=1;	y=0;
		return;
	}
	ExGcd(b,a%b,x,y);
	LL t=x;
	x=y;	y=t-(a/b)*y;
}
 
int main(){
	#ifdef SUBMIT
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	#endif
	scanf("%lld%lld",&A,&B);
	LL x,y;
	ExGcd(A,B,x,y);
	x%=B;
	x=(x+B)%B;
	printf("%lld",x);
	#ifndef SUBMIT
	getchar();	getchar();
	#endif
	fcl;
}